[R70F]锚点 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的正整数序列 $A = [a_1, a_2, \dots, a_n]$。

现有 $q$ 次相互独立的询问。每次询问给定一个下标 $p$ 和一个正整数 $k$，你需要考虑序列 $A$ 中所有同时满足以下条件的连续子数组：

1. 子数组的长度恰好为 $k$；
2. 子数组包含下标为 $p$ 的元素 $a_p$。

对于每次询问，求所有符合条件的连续子数组的最小值中的最大值。

形式化地，设连续子数组对应的下标区间为 $[l, r]$，你需要求出：

$$\max_{\substack{1 \le l \le p \le r \le n \\ r - l + 1 = k}} \left(\min_{l \le i \le r} a_i\right)$$

格式

输入格式

第一行包含两个正整数 $n, q$，分别表示序列的长度和询问次数。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示序列 $A$。

接下来 $q$ 行，每行包含两个正整数 $p, k$，表示一次询问。其中，$p$ 表示指定下标，$k$ 表示连续子数组的长度。

输出格式

输出 $q$ 行。对于每次询问，输出一行一个整数，表示所有符合条件的连续子数组的最小值中的最大值。

样例

样例输入 #1

5 2
1 5 2 4 3
2 2
3 3

样例输出 #1

2
2

样例解释 #1

对于第一次询问，长度为 $2$ 且包含 $a_2$ 的连续子数组为 $[1, 5]$ 和 $[5, 2]$，它们的最小值分别为 $1$ 和 $2$，因此答案为 $2$。

对于第二次询问，长度为 $3$ 且包含 $a_3$ 的连续子数组为 $[1, 5, 2]$、$[5, 2, 4]$ 和 $[2, 4, 3]$，它们的最小值分别为 $1$、$2$ 和 $2$，因此答案为 $2$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n,q\le$
$1$	$10$	$100$
$2$	$20$	$5000$
$3$	$70$	$10^5$

对于 $100\%$ 的数据，满足 $1 \le n, q \le 10^5$，$1 \le a_i \le 10^9$；对于每次询问，满足 $1 \le p, k \le n$。