MloVtry's Brain-Pit Idea Exchange

MloVtry is known for his quirky ideas. He has n ideas arranged in a line inside his two-dimensional brain, and each idea has an associated difficulty value a[i] (the higher the value, the more difficult the idea). When MloVtry consults with his brilliant friends, he does not wish to present ideas that are too easy or impossibly hard. Therefore, during each exchange, he chooses the k-th easiest idea from his current list.

However, there is a twist: a moving "brain-pit" (denoted by its position j) alters his idea difficulties. When the pit is located at the j-th idea, the difficulties are updated as follows:

• For every idea with index i ≤ j:
  \(a[i] = a[i] - j\)
• For every idea with index i > j:
  \(a[i] = a[i] + i - j\)

In other words, if the pit is at position \(j = at\) (provided in the query), then after applying the update, the new difficulty for each idea becomes:

[ new_a[i] = \begin{cases} a[i] - at, & \text{if } i \le at,
a[i] + i - at, & \text{if } i > at. \end{cases} ]

However, note that adding a common \(-at\) to every element does not affect the relative order. In fact, if we add \(at\) back to each element we have:

[ \text{For } i \le at: \quad a[i] \quad \text{and for } i > at: \quad a[i] + i. ]

Thus, for a given query with parameters (at, k), consider two segments:

• Segment 1 (indices 1 to at): values are a[i]
• Segment 2 (indices at+1 to n): values are a[i] + i

If you merge the two segments in sorted order, the answer to the query is the k-th smallest number minus at.

Your task is to answer q queries. Each query provides a tuple (at, k). For each query, update the list as specified and report the difficulty of the k-th easiest idea after subtracting at.

inputFormat

The first line contains a single integer n indicating the number of ideas.

The second line contains n space-separated integers: a[1], a[2], ..., a[n], representing the difficulty values of the ideas.

The third line contains a single integer q representing the number of queries.

Each of the following q lines contains two space-separated integers at and k, representing a query where the pit is at the at-th idea and MloVtry wants to know the k-th easiest idea after the update.

outputFormat

For each query, output a single integer: the difficulty value of the chosen idea after applying the pit update.

sample

5
3 1 4 1 5
3
2 3
3 2
5 4

3
0
-1

</p>