题目描述

$N$ 個の色の付いた玉が左右一列に並んでおり、左から $i$ 番目の玉の色は $c_i$ です。

クエリが $Q$ 個与えられます。$i$ 番目のクエリでは、左から $l_i$ 番目から $r_i$ 番目までにある玉の色の種類数を答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $c_1$ $c_2$ $\cdots$ $c_N$ $l_1$ $r_1$ $l_2$ $r_2$ $:$ $l_Q$ $r_Q$

输出格式

$Q$ 行出力せよ。$i$ 行目には、$i$ 番目のクエリに対する答えを出力せよ。

题目大意

有 $n$ 个数 $a_1,a_2\dots a_n$。有 $q$ 个询问 $l,r$，求从 $l$ 到 $r$ 有多少个不同的元素。

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

提示

制約

• $1\leq\ N,Q\ \leq\ 5\ \times\ 10^5$
• $1\leq\ c_i\ \leq\ N$
• $1\leq\ l_i\ \leq\ r_i\ \leq\ N$
• 入力はすべて整数である。

Sample Explanation 1

- $1,2,3$ 番目の玉の色は $1,2,1$ で、色 $1,2$ の $2$ 種類があります。 - $2,3,4$ 番目の玉の色は $2,1,3$ で、色 $1,2,3$ の $3$ 種類があります。 - $3$ 番目の玉の色は $1$ で、色 $1$ の $1$ 種類があります。