← 返回题目列表

Codeforces · 1900/F

F. 本地删除

中文机器翻译题面 查看原题

对于数组 $$$b_1, b_2, \ldots, b_m$$$,对于某些 $$$i$$$ ($$$1 < i < m$$$),如果 $$$b_i < b_{i-1}$$$ 且 $$$b_i < b_{i+1}$$$,则元素 $$$b_i$$$ 被称为局部最小值。如果 $$$b_1 < b_2$$$,则元素 $$$b_1$$$ 被称为局部最小值。如果 $$$b_m < b_{m-1}$$$,则元素 $$$b_m$$$ 被称为局部最小值。

对于数组 $$$b_1, b_2, \ldots, b_m$$$,对于某些 $$$i$$$ ($$$1 < i < m$$$),如果 $$$b_i > b_{i-1}$$$ 且 $$$b_i > b_{i+1}$$$,则元素 $$$b_i$$$ 被称为局部最大值。如果 $$$b_1 > b_2$$$,则元素 $$$b_1$$$ 被称为局部最大值。如果 $$$b_m > b_{m-1}$$$,则元素 $$$b_m$$$ 被称为局部最大值。

令 $$$x$$$ 为不同元素的数组。我们对其定义了两个操作:

- $$$1$$$ — 删除 $$$x$$$ 中非局部最小值的所有元素。
- $$$2$$$ — 删除 $$$x$$$ 中非局部最大值的所有元素。

定义 $$$f(x)$$$ 如下。按该顺序重复操作 $$$1, 2, 1, 2, \ldots$$$,直到数组中只剩下一个元素。返回该元素。

例如,采用数组 $$$[1,3,2]$$$。我们首先执行 $$$1$$$ 操作并得到 $$$[1, 2]$$$。然后我们执行$$$2$$$类型运算并得到$$$[2]$$$。因此,$$$f([1,3,2]) = 2$$$。

您将获得一个大小为 $$$n$$$ 的排列$$$^\dagger$$$ $$$a$$$ 和 $$$q$$$ 查询。每个查询由两个整数 $$$l$$$ 和 $$$r$$$ 组成,使得 $$$1 \le l \le r \le n$$$。该查询要求您计算 $$$f([a_l, a_{l+1}, \ldots, a_r])$$$。

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是从 $$$1$$$ 到 $$$n$$$ 的任意顺序的 $$$n$$$ 个不同整数的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现了两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$,但数组中有$$$4$$$)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^5$$$) - 排列 $$$a$$$ 的长度和查询数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 排列 $$$a$$$ 的元素。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) - 第 $$$i$$$ 查询的描述。

输出

对于每个查询,输出一个整数 - 该查询的答案。

示例

输入 #1

7 5
1 4 3 6 2 7 5
1 1
1 2
2 3
1 4
1 7

输出 #1

1
1
3
3
3

输入 #2

10 1
1 2 3 4 5 6 7 8 9 10
1 10

输出 #2

1

注意

在第一个示例的第一个查询中,子数组中唯一的数字是 $$$1$$$,因此它是答案。

在第一个示例的第二个查询中,我们的子数组最初看起来像 $$$[1, 4]$$$。执行 $$$1$$$ 类型操作后,我们得到 $$$[1]$$$。

在第一个示例的第三个查询中,我们的子数组最初看起来像 $$$[4, 3]$$$。执行 $$$1$$$ 类型操作后,我们得到 $$$[3]$$$。

在第一个示例的第四个查询中,我们的子数组最初看起来像 $$$[1, 4, 3, 6]$$$。执行 $$$1$$$ 类型操作后,我们得到 $$$[1, 3]$$$。然后我们执行$$$2$$$类型运算,得到$$$[3]$$$。

在第一个示例的第五个查询中,我们的子数组最初看起来像 $$$[1, 4, 3, 6, 2, 7, 5]$$$。执行 $$$1$$$ 类型操作后,我们得到 $$$[1,3,2,5]$$$。执行 $$$2$$$ 类型操作后,我们得到 $$$[3,5]$$$。然后我们执行$$$1$$$类型运算,得到$$$[3]$$$。

在第二个示例的第一个也是唯一一个查询中,我们的子数组最初看起来像 $$$[1,2,3,4,5,6,7,8,9,10]$$$。这里 $$$1$$$ 是唯一的局部最小值,因此执行 $$$1$$$ 类型操作后只剩下它。