Dining Hall Support Dispatch

Soldiers from units near the military dining hall go to the hall to help with its work. This duty is called dining support. The dining support officer decides who goes on dining support and when.

At first, the officer sent three soldiers chosen at random to the hall each day. Tired of picking them by hand every day, the officer built a dispatch program to make the selection simpler and more systematic.

The dispatch program runs every morning and picks soldiers in order of how few dining support duties they have had on that day. Specifically, it selects the three soldiers with the smallest sum of two counts: the number of times they were picked at random before the program started, and the number of times the program picked them from its first day up to the day before the current dispatch. If two soldiers have the same count, the one with the smaller service number is picked first.

Now the soldiers know the dispatch is not random, and they want to know the results in advance. They have started calling the officer to ask how many times the program will pick them through day $d$ of operation. Given the number of days $d$ and a soldier's service number, find how many times the program picks that soldier.

The first line contains the number of soldiers $N$. $(3 \le N \le 10\,000)$

The second line contains $a_1, a_2, \cdots, a_N$, the number of times each soldier from service number $1$ to $N$ was picked at random before the program started, separated by spaces. $(1 \le a_i \le 30)$

The third line contains the number of calls $Q$. $(1 \le Q \le 100\,000)$

The next $Q$ lines each contain a day $d_i$ and a service number $x_i$, separated by a space. $(1 \le d_i \le 10^9; 1 \le x_i \le N)$

For each call, in the order the calls were received, print one integer on its own line: the number of times the program picks that soldier through day $d$.