P1044异色飞羽（beads）

【题目背景】

道路规划完成后，主营地开始与各处聚落定期通信。每条传信路线都使用一种固定颜色作为标记，信使飞鸟抵达主营地时，也会带回具有对应颜色的羽毛。

近来送达的消息越来越多，纸面记录中难免出现重叠和遗漏。tfbz 决定保留这些羽毛，并按照飞鸟抵达的顺序将它们整理起来，以便随时还原某一段时间内真正启用过的传信路线。

【题目描述】

每只信使飞鸟抵达主营地时，tfbz 都会取下一根用于标记路线的羽毛。不同路线采用不同颜色的羽毛，同一条路线留下的羽毛颜色相同。同一条路线可能在一段时间内多次送达消息，因此相同颜色也可能在记录中反复出现。

经过一段时间，tfbz 一共收集了 $n$ 根羽毛，并按照抵达顺序将它们排成一列。第 $i$ 根羽毛的颜色编号为 $a_i$。这列羽毛的顺序不会被改变，因为其中一段连续的位置恰好对应一段连续的通信记录。

SinCircle 从传信记录中选出了 $q$ 个时间段，希望确认这些时间段内分别有多少条路线送达过消息。第 $i$ 次询问给出两个整数 $l_i,r_i$，表示从第 $l_i$ 根羽毛被收集开始，到第 $r_i$ 根羽毛被收集结束的完整记录。

对于每次询问，你需要统计第 $l_i$ 根至第 $r_i$ 根羽毛中出现了多少种不同的颜色。若某种颜色在这段记录中出现过，就说明对应路线曾经送达消息。同一种颜色即使出现多次，也只会被统计一次。

请你按照询问顺序依次输出答案，帮助 tfbz 完成这份传信记录。

【输入格式】

从文件 $\textbf{\textit{beads.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,q$，分别表示羽毛数量与询问数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，依次表示每根羽毛的颜色编号。

接下来 $q$ 行，每行包含两个正整数 $l_i,r_i$，表示一次询问。

【输出格式】

输出到文件 $\textbf{\textit{beads.out}}$ 中。

对于每次询问输出一行一个整数，表示对应区间内不同颜色的数量。

【样例 1 输入】

10 225 532 1 3 2 143 352 362 471 283 596 4101 1 2 3 2 1111 6122 5133 4144 4

【样例 1 输出】

112233425363738291

【说明/提示】

【样例 1 解释】

第一组测试数据的第三次询问包含颜色 $1,2,3$，因此答案为 $3$。

第二组测试数据的第一次询问覆盖全部 $6$ 根羽毛，其中出现了颜色 $1,2,3$，因此答案为 $3$。第四次询问只包含一根羽毛，因此答案为 $1$。

【样例 2】

见选手目录下的 $\textbf{\textit{beads/beads2.in}}$ 和 $\textbf{\textit{beads/beads2.ans}}$。

该组样例符合测试点 $1\sim 5$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{beads/beads3.in}}$ 和 $\textbf{\textit{beads/beads3.ans}}$。

该组样例符合测试点 $6\sim 10$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{beads/beads4.in}}$ 和 $\textbf{\textit{beads/beads4.ans}}$。

该组样例符合测试点 $11\sim 14$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{beads/beads5.in}}$ 和 $\textbf{\textit{beads/beads5.ans}}$。

该组样例符合测试点 $15\sim 19$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{beads/beads6.in}}$ 和 $\textbf{\textit{beads/beads6.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$1\leq n,q\leq 10^6$，单个测试点内 $\sum n\leq 10^6$ 且 $\sum q\leq 10^6$，$1\leq a_i\leq 10^6$，$1\leq l_i\leq r_i\leq n$。

特殊性质 A：保证每次询问均满足 $l_i=1$。

特殊性质 B：保证询问按照输入顺序满足 $r_1\leq r_2\leq\cdots\leq r_q$。