4006: 【NOIP2022赛前集训】合法区间(seg)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：36
解决：1
题目描述
seg.in/out/cpp
给定一个长度为 $n$ 的序列 $a$。你需要回答 $m$ 次询问。
每次询问一个区间 $[l,r]$ 的最长合法子区间。
一个区间 $[l,r]$ 合法，当前仅当 $a_l,a_r$ 或 $a_r,a_l$ 分别是区间最大值和最小值。
例如 $[1,2,3],[2,2],[3,2,1],[3],[2,8,2,3,9]$ 这些都是合法区间。而 $[2,1,2],[1,2,3,4,3]$ 不是合法区间。
给定一个长度为 $n$ 的序列 $a$。你需要回答 $m$ 次询问。
每次询问一个区间 $[l,r]$ 的最长合法子区间。
一个区间 $[l,r]$ 合法，当前仅当 $a_l,a_r$ 或 $a_r,a_l$ 分别是区间最大值和最小值。
例如 $[1,2,3],[2,2],[3,2,1],[3],[2,8,2,3,9]$ 这些都是合法区间。而 $[2,1,2],[1,2,3,4,3]$ 不是合法区间。
输入
第一行两个整数分别表示 $n,m$。
第二行 $n$ 个整数表示序列 $a$。
接下来 $m$ 行每行两个数表示询问的区间 $[l,r]$。
第二行 $n$ 个整数表示序列 $a$。
接下来 $m$ 行每行两个数表示询问的区间 $[l,r]$。
输出
输出 $m$ 行，对应每个询问的答案。
样例输入 复制
5 5
10 8 4 8 2
5 5
1 3
2 3
1 5
1 4样例输出 复制
1
3
2
5
3提示
样例 #2
样例输入 #2
```
30 30
7 12 11 1 18 9 13 11 6 10 6 19 12 6 2 11 16 12 11 5 6 14 2 2 11 4 3 11 3 17
8 20
6 30
16 20
28 29
12 25
1 8
2 6
8 22
3 28
5 16
7 19
12 27
6 26
8 26
27 28
18 30
14 29
14 20
19 20
1 12
6 24
23 27
12 25
19 27
9 19
2 26
14 22
17 27
7 24
4 24
```
### 样例输出 #2
```
4
16
4
2
13
3
3
4
13
7
5
13
13
13
2
8
8
4
2
9
13
3
13
3
4
13
4
8
13
13
```
提示
对于 $100\%$ 的数据，$n,m\le 5\times 10^5,0\le a_i\le 10^9$。
共 $20$ 个测试点。
对于测试点 $1,2$，$n,m\le 100$。
对于测试点 $3,4,5$，$n,m\le 5000$。
对于测试点 $6,7,8$，$m=1$。
对于测试点 $9\sim 12$，$n,m\le 3\times 10^4$。