Different sequence

时间限制：1s

空间限制：64MB

题目描述

定义【 全异序列 】：即一段连续的序列满足序列中的数值 互不相同。

请寻找合适的算法以找出序列区间 [L, R] 之间最长全异序列的长度。

数据格式

输入

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

第二行 N 个整数，第 i 个数表示该序列第 i 个数的值；

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

输出

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

样例1

输入：

9 2
172 175 174 171 172 173 176 172 174
0 8
2 6

输出：

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

输出：

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

样例解释

在第一个样例中：

1. 区间 $[0,8]$ 中的最长全异序列为 $[172,175,174,171,173,176]$ ;
2. 区间 $[2,6]$ 中的最长全异序列为 $[174,171,172,173,176]$ 。

数据范围及约定

规定：对所有测试用例，满足 $0 ≤ L ≤ R ≤ N − 1$ 。