Firstly i came up with this solution: https://codeforces.me/contest/1542/submission/121218884 I think it's O(n) in worst cases, and i got TLE. But shouldn't O(n) be sufficient for these constraints?

After the contest I also updated a O(logn) solution, and its similar to others that i saw submitted, but its getting TLE too: https://codeforces.me/contest/1542/submission/121269280

What am I missing here?