Imagine the situation when we want to find such $$$a_j$$$ for any $$$a_i$$$ which will satisfy this:

Thanks to enabl3d we know solution for this task with $$$O(n)$$$ complexity.

**Solution**

Imagine now the situation, when we want to find such $$$a_j$$$ for any $$$x$$$ and $$$[l; r)$$$, which will satisfy this:

First solution I developed was $$$O(n\log^2{n})$$$ complexity and had such algorithm:

**Solution**

But thanks to MrDindows and retrograd we have solution with $$$O(\log{n})$$$ complexity.

**Solution**

It is possible to see this algorithms working on concrete task: 1237D - Balanced Playlist

Solution $$$O(n\log^2{n})$$$ complexity is 732 ms — 62741630

Solution $$$O(n\log{n})$$$ complexity is 77 ms — 62881402

If you have more efficient solution for any of these two tasks then write here in comments.

You could binary search directly on segment tree to achieve $$$log(N)$$$ complexity, using your very same method

I think we can use Cartesian tree to solve it in O(n).

Can't you explain me how exactly? It is interesting enough idea.

Can u please share the implementation .. Thanks in advance..

You can use sparse table which will give minimum in O(1) and it will be total O(NlogN).