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$$$.