对于数组 $$$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$$$ 类型操作后只剩下它。