配点 : $600$ 点

問題文

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

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

制約

• $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_1$ $c_2$ $\cdots$ $c_N$

$l_1$ $r_1$

$l_2$ $r_2$

$:$

$l_Q$ $r_Q$

出力

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

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

2
3
1

• $1,2,3$ 番目の玉の色は $1,2,1$ で、色 $1,2$ の $2$ 種類があります。
• $2,3,4$ 番目の玉の色は $2,1,3$ で、色 $1,2,3$ の $3$ 種類があります。
• $3$ 番目の玉の色は $1$ で、色 $1$ の $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