不同训练值（distinct）

题目描述

$\text{DAMON THRONE}$ 记录了连续 $n$ 天的训练数据，第 $i$ 天的训练值为 $a_i$。

现在有 $q$ 次查询。每次查询给出两个整数 $l,r$，请你计算区间：

中一共有多少种不同的训练值。

注意：相同的训练值无论出现多少次，都只计算一次。

输入格式

第一行包含两个整数 $n,q$，分别表示训练天数和查询次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每天的训练值。

接下来 $q$ 行，每行包含两个整数 $l,r$，表示一次区间查询。

输出格式

对于每次查询，输出一行一个整数，表示区间 $[l,r]$ 中不同训练值的数量。

输入输出样例 #1

输入 #1

8 4
1 2 1 3 2 4 3 5
1 8
2 5
3 7
4 4

输出 #1

5
3
4
1

样例解释 #1

对于第 $1$ 次查询，区间为 $1,2,1,3,2,4,3,5$，其中不同的训练值为 $1,2,3,4,5$，因此答案为 $5$。

对于第 $2$ 次查询，区间为 $2,1,3,2$，其中不同的训练值为 $1,2,3$，因此答案为 $3$。

输入输出样例 #2

输入 #2

6 3
7 7 7 7 7 7
1 6
2 5
3 3

输出 #2

1
1
1

数据范围与约定

对于所有测试数据，保证：

特殊性质 $\text{A}$：保证所有 $a_i$ 互不相同。

特殊性质 $\text{B}$：保证所有 $a_i$ 都相同。

特殊性质 $\text{C}$：保证所有查询都满足 $l=1$。