彩色球

题目描述

有 $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$ 个查询的答案。

样例

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

数据范围

• $1\leq N,Q \leq 5 \times 10^5$
• $1\leq c_i \leq N$
• $1\leq l_i \leq r_i \leq N$
• 输入均为整数。