CF1900F Local Deletions

对于一个数组 $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$ 的排列 $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$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个询问的区间。

对于每个询问，输出一个整数，表示该询问的答案。

在第一个样例的第一个询问中，子数组中只有一个数字 $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$。 由 ChatGPT 4.1 翻译