This is the problem. I am using sparse table and implementing it exactly as given in the editorial but I am getting, TLE on test 3. I have been stuck for 2 days now on this:-(

Can anyone point out the mistake? Thanks.

This is my submission : 124743771

Let's look at the last

`for`

cycle in your solution. For every i your solution bruteforces all possible values of j (in increasing order). If array is something like this: $$$[2, 4, 6, 8, 10, ..., 2n]$$$ then for every i the correct j is n — i. In total, there would be $$$n + (n - 1) + ... + 1 = \frac{n(n - 1)}{2} = O(n^2)$$$ checks, it is too slow.Instead of this, you should binary search on j. Then you wouldn't check more than $$$O(n\log{n})$$$ indices, that is much better.

NOTE:You might want to optimize your`power`

function. It works in $$$O(\log{x})$$$, so if you will write binary search, the total complexity will be $$$O(n\log^2{n})$$$. It could also TLE. You can precompute all the logarithms in some array, thus deleting extra log factor.The

`power`

function could also be written like:`return 31-__builtin_clz(x);`

to get rid of a factor of`log(n)`

Thanks a lot. Really understood well where I was going wrong.

I am also facing a similar difficulty. I've used a segment tree for this problem and I am getting TLE in test 5.

My Submission. Any help would be appreciated!