310859: CF1900F. Local Deletions

F. Local Deletionstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

For an array $b_1, b_2, \ldots, b_m$, for some $i$ ($1 < i < m$), element $b_i$ is said to be a local maximum if $b_i > b_{i-1}$ and $b_i > b_{i+1}$. Element $b_1$ is said to be a local maximum if $b_1 > b_2$. Element $b_m$ is said to be a local maximum if $b_m > 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).

Input

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.

Output

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

ExamplesInput

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

Output

1
1
3
3
3

Input

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

Output

1

Note

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.

题目大意：对于一个数组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, \ldots, b_m，如果存在某个i (1 < i < m)，使得b_i > b_{i-1} 且 b_i > b_{i+1}，则称b_i为局部最大值。给定一个由不同元素组成的数组x，定义两种操作：1. 删除所有不是局部最小值的元素；2. 删除所有不是局部最大值的元素。定义f(x)如下：重复执行操作1, 2, 1, 2, \ldots，直到数组中只剩下一个元素，返回该元素。给定一个长度为n的排列a和一个查询数q，每个查询包含两个整数l和r，要求计算f([a_l, a_{l+1}, \ldots, a_r])。

输入输出数据格式：
输入：
- 第一行包含两个整数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行，每行包含两个整数l_i和r_i（1 \le l_i \le r_i \le n）——第i个查询的描述。

输出：
- 对于每个查询，输出一个整数——该查询的答案。题目大意：对于一个数组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, \ldots, b_m，如果存在某个i (1 < i < m)，使得b_i > b_{i-1} 且 b_i > b_{i+1}，则称b_i为局部最大值。给定一个由不同元素组成的数组x，定义两种操作：1. 删除所有不是局部最小值的元素；2. 删除所有不是局部最大值的元素。定义f(x)如下：重复执行操作1, 2, 1, 2, \ldots，直到数组中只剩下一个元素，返回该元素。给定一个长度为n的排列a和一个查询数q，每个查询包含两个整数l和r，要求计算f([a_l, a_{l+1}, \ldots, a_r])。 输入输出数据格式： 输入： - 第一行包含两个整数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行，每行包含两个整数l_i和r_i（1 \le l_i \le r_i \le n）——第i个查询的描述。 输出： - 对于每个查询，输出一个整数——该查询的答案。