407402: GYM102784 I Candy Supply

Katarina has done her research going into this year's Halloween season. She knows about the quality of candy that each and every house in the neighborhood will be giving out to trick or treaters this year. The houses in the neighborhood can be viewed as being evenly spaced across a line, and trick or treaters can travel left or right to move between houses.

Katarina has decided to help out her friends using her research by telling them what the closest house to them that provides candy of the required quality. Given the locations of all of Katarina's friends and the qualities of candies that they want, can Katarina efficiently tell each friend where the closest house that meets their desired quality is (if one exists)?

For each friend, output the index of the closest house that meets that friend's desired candy quality. If there is a tie between two houses, output the one with minimum index. If no such house exists, output $$$-1$$$.

The first line will consist of a two space-separated integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) giving the number of houses and number of friend queries that Katarina must answer, respectively. The next line will consist of $$$n$$$ numbers $$$a_i$$$ ($$$0 \leq a_i \leq 10^5$$$), which gives the quality of candy at the $$$i$$$th house. The next $$$q$$$ lines will consist of two integers $$$l$$$ and $$$v$$$, indicating that the current friend is currently at index $$$l$$$ ($$$0 \leq l < n$$$) and wants candy that has quality that is $$$\geq v$$$ $$$(0 \leq v \leq 10^5)$$$.

For each friend query, output a single integer giving the zero-based index of the closest house that meets the friend's quality constraint followed by a new line. If there are multiple such houses, output the minimum such index. If no such house exists, output $$$-1$$$.

9 4
5 4 3 2 1 2 3 4 5
4 4
5 4
4 5
3 6

1
7
0
-1

10 5
2 8 4 7 11 10 6 6 3 11
9 2
9 3
0 8
2 7
6 6

9
9
1
1
6