It's been quite a long journey from the airport to the building of secrets. BMP and MSA have come across a room full of different elevators. You know for a fact that there are exactly ~N~ elevators, with the ~i~-th elevator initially located on floor ~A_i~. They do not have much time, so they have to call the closest elevator to them. The building has an interesting quirk though. More elevators were added over the years, which means the newer ones (the elevators that are numbered higher) are faster. Using this knowledge, you decide that if two elevators are at an equal distance from a certain floor, the newer elevator will show up first.

Right now BMP and MSA are busy working on their plan for getting the formula and escaping, which leaves you to decide on the best elevator to choose for various scenarios. There are exactly ~R~ scenarios.

In the ~j~-th scenario, they are on floor ~S_j~ and want to travel to floor ~E_j~. They will call the elevator closest to floor ~S_j~, and use it to go to floor ~E_j~, leaving it there for future queries.

Input Specification

The first line consists of a single integer ~N~ ~(1 \le N \le 100)~, the number of elevators.

The following ~N~ lines each contain a single integer ~A_i~ ~(1 \le A_i \le 100)~, the initial position of the ~i~-th elevator.

The next line consists of a single integer ~R~ ~(1 \le R \le 100)~, the number of scenarios.

Next ~R~ lines contain two space separated integers ~S_j~ ~(1 \le S_j \le 1\,000)~ and ~E_j~ ~(1 \le E_j \le 1\,000)~, representing the starting and ending floors in the ~j~-th scenario.

Output Specification

For each of the ~R~ scenarios, output an integer representing the number of the elevator that is closest for the particular scenario.

Sample Input

3
1
9
8
3
3 4
4 7
10 1

Sample Output

1
1
2