I. Two Sequences
data structures; hashing; string suffix structures
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]\).