Hi everyone, please consider the following submission:

https://mirror.codeforces.com/problemset/submission/1467/215118514

The code is in O(n), yet I'm getting TLE. I changed cin to scanf. In that I got my answer different on CF server and local machine. So, I changed it back to cin.

I don't think I'm calling too many functions. They all run in O(1) time.