CF1900F.Local Deletions

For an array $b_1, b_2, \ldots, b_m$, for some $i$ ($1 \lt i \lt m$), element $b_i$ is said to be a local minimum if $b_i \lt b_{i-1}$ and $b_i \lt b_{i+1}$. Element $b_1$ is said to be a local minimum if $b_1 \lt b_2$. Element $b_m$ is said to be a local minimum if $b_m \lt b_{m-1}$.

For an array $b_1, b_2, \ldots, b_m$, for some $i$ ($1 \lt i \lt m$), element $b_i$ is said to be a local maximum if $b_i \gt b_{i-1}$ and $b_i \gt b_{i+1}$. Element $b_1$ is said to be a local maximum if $b_1 \gt b_2$. Element $b_m$ is said to be a local maximum if $b_m \gt b_{m-1}$.

Let $x$ be an array of distinct elements. We define two operations on it:

• $1$ — delete all elements from $x$ that are not local minima.
• $2$ — delete all elements from $x$ that are not local maxima.

Define $f(x)$ as follows. Repeat operations $1, 2, 1, 2, \ldots$ in that order until you get only one element left in the array. Return that element.

For example, take an array $[1,3,2]$. We will first do type $1$ operation and get $[1, 2]$. Then we will perform type $2$ operation and get $[2]$. Therefore, $f([1,3,2]) = 2$.

You are given a permutation$^\dagger$ $a$ of size $n$ and $q$ queries. Each query consists of two integers $l$ and $r$ such that $1 \le l \le r \le n$. The query asks you to compute $f([a_l, a_{l+1}, \ldots, a_r])$.

$^\dagger$ A permutation of length $n$ is an array of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$, but there is $4$ in the array).

对于数组 $b_1, b_2, \ldots, b_m$，对某个下标 $i$（其中 $1 \lt i \lt m$），若满足 $b_i \lt b_{i-1}$ 且 $b_i \lt b_{i+1}$，则称元素 $b_i$ 为局部最小值；若 $b_1 \lt b_2$，则称 $b_1$ 为局部最小值；若 $b_m \lt b_{m-1}$，则称 $b_m$ 为局部最小值。

对于数组 $b_1, b_2, \ldots, b_m$，对某个下标 $i$（其中 $1 \lt i \lt m$），若满足 $b_i \gt b_{i-1}$ 且 $b_i \gt b_{i+1}$，则称元素 $b_i$ 为局部最大值；若 $b_1 \gt b_2$，则称 $b_1$ 为局部最大值；若 $b_m \gt 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$）。

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$) — the length of the permutation $a$ and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of permutation $a$.

The $i$-th of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the description of $i$-th query.

第一行包含两个整数 $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$ 个查询。

For each query, output a single integer — the answer to that query.

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

In the first query of the first example, the only number in the subarray is $1$, therefore it is the answer.

In the second query of the first example, our subarray initially looks like $[1, 4]$. After performing type $1$ operation we get $[1]$.

In the third query of the first example, our subarray initially looks like $[4, 3]$. After performing type $1$ operation we get $[3]$.

In the fourth query of the first example, our subarray initially looks like $[1, 4, 3, 6]$. After performing type $1$ operation we get $[1, 3]$. Then we perform type $2$ operation and we get $[3]$.

In the fifth query of the first example, our subarray initially looks like $[1, 4, 3, 6, 2, 7, 5]$. After performing type $1$ operation we get $[1,3,2,5]$. After performing type $2$ operation we get $[3,5]$. Then we perform type $1$ operation and we get $[3]$.

In the first and only query of the second example our subarray initially looks like $[1,2,3,4,5,6,7,8,9,10]$. Here $1$ is the only local minimum, so only it is left after performing type $1$ operation.

在第一个样例的第一个查询中，子数组中唯一的数字是 $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$ 操作后仅剩 $1$。