I tired about 70 times this question, resulting in TLE. Has anyone got an O(n^2) solution accepted ?. Just a yes or no is required.
n = 10^5 => n^2 = 10^10, which is obviously too much.
I also have a O(n^2) solution, but the question demands an O(n) solution. so, we have to change the approach
Talking not only about this problem but whenever you are solving any algorithmic problem where N >= 10^4, Right from the starting think about O(N) solution because they gonna have at least one test case of MAX(N) where your O(N^2) will always get timed out. N^2 may pass provided they don’t have strict time limit. Similarly O(N) will time out for N >= 10^15 , Think about O(1) solution for this, As MAX(N) may go up to 10^18 in some problem. That’s it 
Correct me if I am wrong.
Just one more thing, Trying 70 times is too much. You just need to create a test case of 10^5 locally, Run your code on this input and at the very moment your program takes more than 1-2 seconds. Abort it because the algorithm you used is obviously going to get TLE on Codechef servers, which are mostly slower than your high end laptops. Think about a better approach. Its saves you 69 tries.