题目描述

我们有$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$个查询的响应。

示例输入1

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

示例输出1

2
3
1

• 从左边数第$1$、$2$和$3$个球分别为$1$、$2$和$1$号颜色-两种不同的颜色。
• 从左边数第$2$、$3$和$4$个球分别为$2$、$1$和$3$号颜色-三种不同的颜色。
• 从左边数第$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