CF1621I.Two Sequences

Consider an array of integers $C = [c_1, c_2, \ldots, c_n]$ of length $n$ . Let's build the sequence of arrays $D_0, D_1, D_2, \ldots, D_{n}$ of length $n+1$ in the following way:

• The first element of this sequence will be equals $C$ : $D_0 = C$ .
• For each $1 \leq i \leq n$ array $D_i$ will be constructed from $D_{i-1}$ in the following way:
  • Let's find the lexicographically smallest subarray of $D_{i-1}$ of length $i$ . Then, the first $n-i$ elements of $D_i$ will be equals to the corresponding $n-i$ elements of array $D_{i-1}$ and the last $i$ elements of $D_i$ will be equals to the corresponding elements of the found subarray of length $i$ .

Array $x$ is subarray of array $y$ , if $x$ can be obtained by deletion of several (possibly, zero or all) elements from the beginning of $y$ and several (possibly, zero or all) elements from the end of $y$ .

For array $C$ let's denote array $D_n$ as $op(C)$ .

Alice has an array of integers $A = [a_1, a_2, \ldots, a_n]$ of length $n$ . She will build the sequence of arrays $B_0, B_1, \ldots, B_n$ of length $n+1$ in the following way:

• The first element of this sequence will be equals $A$ : $B_0 = A$ .
• For each $1 \leq i \leq n$ array $B_i$ will be equals $op(B_{i-1})$ , where $op$ is the transformation described above.

She will ask you $q$ queries about elements of sequence of arrays $B_0, B_1, \ldots, B_n$ . Each query consists of two integers $i$ and $j$ , and the answer to this query is the value of the $j$ -th element of array $B_i$ .

The first line contains the single integer $n$ ( $1 \leq n \leq 10^5$ ) — the length of array $A$ .

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq n$ ) — the array $A$ .

The third line contains the single integer $q$ ( $1 \leq q \leq 10^6$ ) — the number of queries.

Each of the next $q$ lines contains two integers $i$ , $j$ ( $1 \leq i, j \leq n$ ) — parameters of queries.

Output $q$ integers: values of $B_{i, j}$ for required $i$ , $j$ .

In the first test case $B_0 = A = [2, 1, 3, 1]$ .

$B_1$ is constructed in the following way:

• Initially, $D_0 = [2, 1, 3, 1]$ .
• For $i=1$ the lexicographically smallest subarray of $D_0$ of length $1$ is $[1]$ , so $D_1$ will be $[2, 1, 3, 1]$ .
• For $i=2$ the lexicographically smallest subarray of $D_1$ of length $2$ is $[1, 3]$ , so $D_2$ will be $[2, 1, 1, 3]$ .
• For $i=3$ the lexicographically smallest subarray of $D_2$ of length $3$ is $[1, 1, 3]$ , so $D_3$ will be $[2, 1, 1, 3]$ .
• For $i=4$ the lexicographically smallest subarray of $D_3$ of length $4$ is $[2, 1, 1, 3]$ , so $D_4$ will be $[2, 1, 1, 3]$ .
• So, $B_1 = op(B_0) = op([2, 1, 3, 1]) = [2, 1, 1, 3]$ .