AT_abc174_f.[ABC174F] Range Set Query

有 $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$ $\cdots$ $l_Q$ $r_Q$

请输出 $Q$ 行。第 $i$ 行输出第 $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$
• 所有输入均为整数。

样例解释 1

• 第 $1,2,3$ 个珠子的颜色分别为 $1,2,1$，其中有 $2$ 种颜色：$1,2$。
• 第 $2,3,4$ 个珠子的颜色分别为 $2,1,3$，其中有 $3$ 种颜色：$1,2,3$。
• 第 $3$ 个珠子的颜色为 $1$，其中有 $1$ 种颜色：$1$。

由 ChatGPT 4.1 翻译