数组段数
题号：NC266837
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小蓝获得了一个长度为 n 的数组：A_1,A_2,...,A_n。

小红对小灰灰提出了 m 个询问，第 i 个询问给出两个参数 l_i, r_i 代表小红截取了原数组的 A_{l_i}, A_{l_i + 1}, ..., A_{r_i} 部分。

对于每个询问，小灰灰想知道小红截取出的数组有多少段。

一个长度为 s 的数组 B_1, B_2, ..., B_s，其段数被定义为最小的 k 使得将数组划分成连续的 k 段后，每个元素都属于某一段，且每段数组中的元素种类应该全部相同。

输入描述:

输入第一行包含两个空格分隔的整数 n，m 分别代表数组长度和询问个数。

接下来一行输入 n 个空格分隔的整数分别代表：A_1, A_2, ..., A_n。

接下来 m 行，第 i 行包含两个空格分隔的整数 l_i\ r_i 代表第 i 个询问给出的两个参数。

保证：
1 \le n,m \le 2\times10^5 

1 \le A_i \le 10^6 

1\le l_i\le r_i\le n

输出描述:

输出共 m 行，第 i 行代表第 i 个询问的答案。
示例1

输入

复制 
6 4
2 2 3 1 3 3
1 3
2 5
2 2
4 6

输出

复制 
2
4
1
2

说明

对于询问区间 [1, 3] 所在的子数组 \lbrace 2, 2, 3 \rbrace 其最少可以被划分为 2 段：\lbrace 2,2 \rbrace,\lbrace3\rbrace。

对于询问区间 [2, 5] 所在的子数组 \lbrace 2, 3, 1, 3 \rbrace 其最少可以被划分为 4 段：\lbrace 2\rbrace,\lbrace 3\rbrace,\lbrace 1\rbrace,\lbrace3\rbrace。

对于询问区间 [2, 2] 所在的子数组 \lbrace 2 \rbrace 其最少可以被划分为 1 段：\lbrace2\rbrace。

对于询问区间 [4, 6] 所在的子数组 \lbrace 1, 3, 3 \rbrace 其最少可以被划分为 2 段：\lbrace 1\rbrace,\lbrace3,3\rbrace。