TSOC '15 Contest 1 #3 - Elevators

View as PDF

Submit solution

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

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

Input Specification

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.

Output Specification

For R scenarios, a single 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.