Answering online queries is tough. Try to answer them offline since the queries are known beforehand.

For each index, how do you calculate the left boundary so that the given condition is satisfied?

Using the precomputed left boundaries and a range data structure, you can now answer the queries optimally.