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

考虑一个长度为 $n$ 的整数数组 $C = [c_1, c_2, \ldots, c_n]$。我们按如下方式构造长度为 $n+1$ 的数组序列 $D_0, D_1, D_2, \ldots, D_{n}$：

• 该序列的第一个数组即为 $C$：$D_0 = C$。
• 对每个 $1 \leq i \leq n$，数组 $D_i$ 由 $D_{i-1}$ 按如下方式构造：
  • 找出 $D_{i-1}$ 中字典序最小的长度为 $i$ 的子数组；然后，$D_i$ 的前 $n-i$ 个元素等于 $D_{i-1}$ 中对应的前 $n-i$ 个元素，而 $D_i$ 的后 $i$ 个元素等于所找到的长度为 $i$ 的子数组中对应的元素。

若数组 $x$ 可通过从数组 $y$ 的开头删除若干（可能为零个或全部）元素、并从其末尾删除若干（可能为零个或全部）元素而得到，则称 $x$ 是 $y$ 的子数组。

对数组 $C$，记 $D_n$ 为 $op(C)$。

Alice 有一个长度为 $n$ 的整数数组 $A = [a_1, a_2, \ldots, a_n]$。她将按如下方式构造长度为 $n+1$ 的数组序列 $B_0, B_1, \ldots, B_n$：

• 该序列的第一个数组即为 $A$：$B_0 = A$。
• 对每个 $1 \leq i \leq n$，数组 $B_i$ 等于 $op(B_{i-1})$，其中 $op$ 即上述定义的变换。

她将向你提出 $q$ 个查询，每个查询针对数组序列 $B_0, B_1, \ldots, B_n$ 中的某个元素。每个查询包含两个整数 $i$ 和 $j$，其答案为数组 $B_i$ 的第 $j$ 个元素的值。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组 $A$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）—— 数组 $A$。

第三行包含一个整数 $q$（$1 \leq q \leq 10^6$）—— 查询的数量。

接下来的 $q$ 行中，每行包含两个整数 $i$、$j$（$1 \leq i, j \leq n$）—— 查询的参数。

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

输出 $q$ 个整数：所需 $i$、$j$ 对应的 $B_{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]$.

在第一个测试用例中，$B_0 = A = [2, 1, 3, 1]$。

$B_1$ 按如下方式构造：

• 初始时，$D_0 = [2, 1, 3, 1]$。
• 当 $i=1$ 时，$D_0$ 中长度为 $1$ 的字典序最小的子数组是 $[1]$，因此 $D_1 = [2, 1, 3, 1]$。
• 当 $i=2$ 时，$D_1$ 中长度为 $2$ 的字典序最小的子数组是 $[1, 3]$，因此 $D_2 = [2, 1, 1, 3]$。
• 当 $i=3$ 时，$D_2$ 中长度为 $3$ 的字典序最小的子数组是 $[1, 1, 3]$，因此 $D_3 = [2, 1, 1, 3]$。
• 当 $i=4$ 时，$D_3$ 中长度为 $4$ 的字典序最小的子数组是 $[2, 1, 1, 3]$，因此 $D_4 = [2, 1, 1, 3]$。
• 因此，$B_1 = op(B_0) = op([2, 1, 3, 1]) = [2, 1, 1, 3]$。