Problem 1B. 完全参差序列

题目背景

2022年，南京师范大学迎来了 120周年校庆 ，值此120周年校庆筹备工作全面启动之际，学校诚邀海内外校友、社会贤达、各界人士壬寅中秋相聚金陵，共赴节日盛典，共商教育大计，共襄发展盛举。但是，小周学长觉得新生也是学校的重要组成，因此决定邀请大家参加校庆聚会；

然而，请来了新生，如何站位却难住了小周学长——新生的能力参差不齐，纯粹按照身高来排列又显得古板，因此小周学长想到了一种特殊的排列方式——【 分段式参差排法-完全参差序列（S-F）】：即一段连续的学生排列满足排列中的学生 综合水平值 （一个根据多方面评判的的数值） 互不相同。

小周学长想知道区间 [L, R] 之间最长 S-F 序列的长度。

输入格式

第一行两个整数 N，M。N 表示连续 N 个学生，编号为 0 到 N−1，M 表示询问的次数；

第二行 N 个整数，第 i 个数表示该学生队列第 i 个学生的 综合水平值 ai；

接下来 M 行每行两个整数 L，R，表示 小周学长 询问的区间。

输出格式

输出 M 行，每行一个整数对应询问区间内的 S-F 序列的最长长度。

数据范围

对于 50% 的数据:

• 1 ≤ N, M ≤ 1000,
• 0 ≤ L ≤ R ≤ N − 1,
• 0 ≤ ai ≤ 10^5.

对于 100% 的数据:

• 1 ≤ N, M ≤ 2 × 10^5,
• 0 ≤ L ≤ R ≤ N − 1,
• 0 ≤ ai ≤ 10^6.

输入样例1：

9 2
2 5 4 1 2 3 6 2 4
0 8
2 6

输出样例1：

6
5

输入样例2：

50 50
725 484 509 297 277 201 695 142 299 565 104 903 564 647 253 533 794 935 831 911 49 305 702 626 627 292 71 733 727 260 121 98 774 908 436 354 446 440 611 504 146 97 956 433 25 258 390 698 382 332 
34 37
1 22
19 47
38 47
14 14
22 46
45 48
34 48
24 30
38 39
31 39
6 43
33 35
8 44
8 33
5 19
6 10
38 44
43 45
16 34
6 39
22 35
43 44
45 49
32 37
2 8
18 41
7 47
18 31
45 46
39 45
26 40
47 48
26 33
17 40
35 46
37 48
13 39
40 48
14 42
1 12
34 39
11 35
33 35
8 27
26 41
4 46
25 43
32 48
27 40

输出样例2：

4
22
29
10
1
25
4
15
7
2
9
38
3
37
26
15
5
7
3
19
34
14
2
5
6
7
24
41
14
2
7
15
2
8
24
12
12
27
9
29
12
6
25
3
20
16
43
19
17
14

时间和空间限制

2s / 64MB