Greetings! My solution to the problem B in Codeforces Round 358 div2 edition, surprisingly failed at 105 th test with verdict 'time limit exceeded'. My code was written in Java, and simply run at O(n) time. I have tried many times by changing Scanner to BufferedReader, but still cannot realize the reason why it cannot pass the time limit. Here is my code. Can somebody guess the reason of failure?

P.S It is not because of Scanner and not because of java compiler version. Moreover I have checked with generated input in my computer and it works fine in about 100 to 250 ms.