I’ve though about this for a couple hours but I’m unable to make much headway. It goes like this :

You have an array of size n and q queries. Each query is of the form (l, r, k). The answer to each query is the index (1-based) of the leftmost number in the range [l, r] which is greater than or equal to k. If there is no such value, return -1. Constraints: n, q <= 1e5, l <= r and the elements can be from 0 to 1e9. The program should run within a second.

Example input :

n = 5, q = 2

7 4 6 9

Queries :

3 4 7

2 4 5

Output:

4

3

I feel like a maximum segment tree might work here, but I am unable to put it together. Please help. Obviously, a O(n^2) solution would not run in time. I think the intended solution is O(nlogn).