题目描述

有 $n$ 个球从左到右排成一排，其中第 $i$ 个球的颜色为 $c_i$。

有 $q$ 次询问，第 $i$ 次询问包含两个整数 $l_i$ 和 $r_i$，你需要回答出从第 $l_i$ 个球到第 $r_i$ 个球一共存在多少种不同的颜色。

输入格式

第一行，两个整数 $n$ 和 $q$，以空格分隔（$1 \le n,q \le 5 \times 10^5$）。

第二行，$n$ 个整数 $c_1, c_2, \ldots, c_n(1 \le c_i \le n)$。

接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示一次询问（$1 \le l_i \le r_i \le n$）。

输出格式

对于每次询问，输出一行，包含一个整数，表示从第 $l_i$ 个球到第 $r_i$ 个球一共存在多少种不同的颜色。

样例

4 3
1 2 1 3
1 3
2 4
3 3

2
3
1

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

1
2
2
1
2
2
6
3
3
3

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,q \le 5000$
• 对于 $100\%$ 的数据，$n,q \le 5 \times 10^5$