TSOC '15 Contest 1 #3 - Elevators

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem type

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

Comments

There are no comments at the moment.