CF1621I Two Sequences

给定一个长度为 $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$ 是上述定义的变换。 她会就数组序列 $B_0, B_1, \ldots, B_n$ 中的元素向你提出 $q$ 个询问。每个询问包含两个整数 $i$ 和 $j$，你需要回答数组 $B_i$ 的第 $j$ 个元素的值。

第一行包含一个整数 $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$），表示一次询问的参数。

输出 $q$ 个整数，依次为每个询问对应的 $B_{i, j}$ 的值。

在第一个测试用例中，$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]$。 由 ChatGPT 4.1 翻译