题目描述

有一个长度为 $n$ 的数组 $a$，其首元素下标为 $1$。再给你 $m$ 个区间 $\left[l_1,r_1\right],\left[l_2,r_2\right],\left[l_3,r_3\right],...,\left[l_m,r_m\right]$，请你求出 $a_{l_i}\sim a_{r_i}$ 中不同数字的个数。

输入格式

第一行两个数 $n$ 和 $m$，用空格隔开；

第二行 $n$ 个数，其中第 $i$ 个表示 $a_i$；

后面 $m$ 行，每行两个数 $l_i$ 和 $r_i$。

输出格式

共 $m$ 行，每行一个数，表示第 $i$ 个区间内不同数字的个数。

输入输出样例

5 1
1 1 4 5 1
1 4

3

10 5
2 3 3 3 3 3 1 9 1 9
1 1
4 5
1 4
1 10
6 9

1
1
2
4
3

数据范围

对于 $30\%$ 的数据：$1\le l\le r\le n\le5000$，$1\le m\le5000$，$0\le a_i\le10000$；

对于另外 $10\%$ 的数据：$m=1$；

对于 $100\%$ 的数据：$1\le l\le r\le n\le10^5$，$1\le m\le2\times10^5$，$0\le a_i\le10^6$。