题目描述

给定一个长度为 $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]$。

输出格式

输出 $m$ 行，对应每个询问的答案。

样例 #1

样例输入 #1

5 5
10 8 4 8 2
5 5
1 3
2 3
1 5
1 4

样例输出 #1

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$。