← 返回题目列表

Codeforces · 1621/I

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}$$$ 按以下方式构造:让我们找到长度为 $$$i$$$ 的 $$$D_{i-1}$$$ 的字典顺序最小子数组。然后,$$$D_i$$$ 的前 $$$n-i$$$ 元素将等于数组 $$$D_{i-1}$$$ 中对应的 $$$n-i$$$ 元素,$$$D_i$$$ 的最后 $$$i$$$ 元素将等于找到的长度为 $$$i$$$ 的子数组的对应元素。

数组 $$$x$$$ 是数组 $$$y$$$ 的子数组,如果 $$$x$$$ 可以通过删除 $$$y$$$ 开头的几个(可能是零个或全部)元素以及从 $$$y$$$ 末尾删除几个(可能是零个或全部)元素来获得。

对于数组 $$$C$$$,我们将数组 $$$D_n$$$ 表示为 $$$op(C)$$$。

Alice 有一个整数数组 $$$A = [a_1, a_2, \ldots, a_n]$$$,长度为 $$$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$$$ 个元素的值。

输入

第一行包含单个整数 $$$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}$$$ 的值,满足所需的 $$$i$$$、$$$j$$$。

示例

输入 #1

4
2 1 3 1
4
1 1
1 2
1 3
1 4

输出 #1

2
1
1
3

注意

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

$$$B_1$$$ 的构造方式如下:

- 最初,$$$D_0 = [2, 1, 3, 1]$$$。
- 对于 $$$i=1$$$,长度为 $$$1$$$ 的 $$$D_0$$$ 按字典顺序最小的子数组是 $$$[1]$$$,因此 $$$D_1$$$ 将是 $$$[2, 1, 3, 1]$$$。
- 对于 $$$i=2$$$,长度为 $$$2$$$ 的 $$$D_1$$$ 按字典顺序最小的子数组是 $$$[1, 3]$$$,因此 $$$D_2$$$ 将是 $$$[2, 1, 1, 3]$$$。
- 对于 $$$i=3$$$,长度为 $$$3$$$ 的 $$$D_2$$$ 按字典顺序最小的子数组是 $$$[1, 1, 3]$$$,因此 $$$D_3$$$ 将是 $$$[2, 1, 1, 3]$$$。
- 对于 $$$i=4$$$,长度为 $$$4$$$ 的 $$$D_3$$$ 按字典顺序最小的子数组是 $$$[2, 1, 1, 3]$$$,因此 $$$D_4$$$ 将是 $$$[2, 1, 1, 3]$$$。
- 所以,$$$B_1 = op(B_0) = op([2, 1, 3, 1]) = [2, 1, 1, 3]$$$。