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. 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.
The first line consists of a single integer ~N~ ~(1 \le N \le 100)~.
The following ~N~ lines contain a single integer that displays the starting position of the elevators. For example, line 2 contains the starting position of elevator 1, line 3 contains the starting position of elevator 2, etc.
Next line consists of a single integer ~R~ ~(1 \le R \le 100)~.
Next ~R~ lines contain two space separated integers: ~S~ ~(1 \le S \le 1\,000)~ and ~E~ ~(1 \le E \le 1\,000)~. ~S~ is the floor number that has requested an elevator, and ~E~ is the floor where the most recent request wants to get off.
For ~R~ scenarios, a single integer representing the number of the elevator that is closest for the particular scenario.
3 1 9 8 3 3 4 4 7 10 1
1 1 2