问题陈述

有 $N$ 个球排成一行，第 $i$ 个球的颜色是 $c_i$。

有 $Q$ 个询问，每次询问一个区间 $[l,r]$， 输出区间内有几种不同颜色的球。

约束条件

$1\leq N,Q \leq 5 \times 10^5$

$1\leq c_i \leq N$

$1\leq l_i \leq r_i \leq N$

输入

第一行 $N, Q$

第二行每个球的颜色 $c_i$

接下来 $Q$ 行，每行一个区间

输出

$Q$ 行，每个询问的答案

样例输入 1

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

样例输出 1

2
3
1

样例输入 2

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

样例输出 2

1
2
2
1
2
2
6
3
3
3