405156: GYM101807 H Handicap

In Hackerland, sports programming is the most popular activity. More than half of its residents has a rating on Hackforces, the official programming competition platform there.

What is so unique about Hackforces is that 1-versus-1 matches are available! Two players can match online and enjoy a battle of wits anytime. The match can be boring though, if, for example, an absolute beginner with rating $$$1$$$ fights a Legendary Grandmaster with rating $$$10^9$$$ - everyone knows the outcome before the match starts.

Therefore, Hackforces has a handicap system, allowing the higher-rated player to play with some disadvantages, thus making the match more even. There are $$$N$$$ types of handicaps, and the $$$i$$$-th one is equivalent to reducing one's rating by $$$D[i]$$$ points. Here are some of them:

• Type With One's Nose - Self-explanatory.
• You Only Submit Once - Only one submission attempt per task.
• Blindfolded - Code while wearing a blindfold.

Seeing that many strong programmers do not voluntarily select a suitable handicap, Hackforces would like to install an auto-handicap feature. Given the ratings of two players $$$X$$$ and $$$Y$$$ ($$$X \le Y$$$), auto-handicap should automatically pick an index $$$i$$$ between $$$1$$$ and $$$N$$$ (inclusive), such that $$$Y - D[i] > 0$$$ and $$$|Y - D[i] - X|$$$ is minimized. In other words, the new rating $$$Y_{new} := Y - D[i]$$$ of the second player should be positive and as close to $$$X$$$ as possible.

There are three subtle details to keep in mind. First, if playing without handicap yields the smallest rating difference, then it is preferred to play without handicap. Second, if none of the handicaps can make $$$Y_{new}$$$ positive, then playing without handicap is the only choice. Third, if two or more different valid handicaps yield the same rating difference, then the one with the smallest index is preferred.

You are to implement this feature to pick the best handicap for $$$Q$$$ matches, according to the rules above.

The first line of input consists of a single integer $$$N$$$.

The second line of input consists of $$$N$$$ space-separated integers $$$D[1], D[2], \dots, D[N]$$$.

The third line of input consists of a single integer $$$Q$$$.

For the next $$$Q$$$ lines of input, the $$$i$$$-th line consists of a pair of integers $$$X_i$$$ and $$$Y_i$$$, the ratings of the two players in the $$$i$$$-th match. It is guaranteed that $$$X_i \le Y_i$$$.

For all test cases, $$$1 \le N, Q \le 10^5$$$, $$$1 \le D[1] < D[2] < \dots < D[N] < 10^9$$$, $$$1 \le X_i \le Y_i \le 10^9$$$.

Output $$$N$$$ lines, the $$$i$$$-th line corresponding to the $$$i$$$-th match.

If the best choice for the $$$i$$$-th match is to play without handicap, output $$$0$$$.

Otherwise, output the index corresponding to the chosen handicap.

5
2 3 5 10 100
5
1 1
1500 1501
1500 1502
1500 1504
10 65

0
0
1
2
4