静态区间不同元素个数（Static Range Count Distinct）

问题描述

给定一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$。
处理 $Q$ 个查询：对每个查询 l r，输出子数组 $a_l, a_{l+1}, \dots, a_{r-1}$ 中不同整数的个数。

约束条件

• $0 \leq N \leq 5 \times 10^5$
• $0 \leq Q \leq 5 \times 10^5$
• $0 \leq a_i \leq 10^9$
• $0 \leq l \leq r \leq N$

输入

$N\ Q$
$a_0\ a_1\ \cdots\ a_{N-1}$
$l_0\ r_0$
$l_1\ r_1$
:
$l_{Q-1}\ r_{Q-1}$

5 3
3 7 1 2 1
1 5
3 3
0 4

3
0
4