I got AC with O(n) ! Several times I got TL, but when I stopped reading the input with java.util.Scanner and started using java.io.BufferedReader it worked.

java.util.Scanner is too slow, don't use it !

thnx, otherwise TL21

class Scanner {

   StreamTokenizer in;

   Scanner(InputStream stream) {
      in = new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
   }

   void asserT(boolean e) {
      if (!e) {
         throw new Error();
      }
   }

   int nextInt() {
      try {
         in.nextToken();
         asserT(in.ttype == in.TT_NUMBER);
         asserT((int) in.nval == in.nval);
         return (int) in.nval;
      } catch (IOException e) {
         throw new Error(e);
      }
   }
}
".. and nothing else matters ..." (c)Metallica