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

Thanks to shufl999dka 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 bicsi 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.