题目描述

给定一个长度为 (n) 的数组，其中每个元素均为非负整数。接下来有 (Q) 次查询，每次查询给定一个区间 ([L, R])（1-indexed），要求统计该区间内出现的不同数字的个数。

输入格式

• 第一行包含两个整数 \(n\) 和 $Q\$ \(1 \le n, Q \le 10^5\) 。
• 第二行包含 $n\$ 个非负整数，表示数组元素。
• 接下来 $Q\$ 行，每行包含两个整数 (L) 和 (R)，表示查询区间(1-indexed，保证 \(1 \le L \le R \le n\) ) 。

输出格式

对于每个查询，输出一行一个整数，表示该区间内不同数字的个数。

样例输入

8 4
1 2 1 3 4 2 1 5
1 4
2 6
3 8
1 8

样例输出

3
4
5
5

说明

• 查询 1：区间 ([1,4]) 对应数组片段为 ([1,2,1,3])，不同数字为 ({1,2,3})，答案为 3。
• 查询 2：区间 ([2,6]) 对应数组片段为 ([2,1,3,4,2])，不同数字为 ({1,2,3,4})，答案为 4。
• 查询 3：区间 ([3,8]) 对应数组片段为 ([1,3,4,2,1,5])，不同数字为 ({1,2,3,4,5})，答案为 5。
• 查询 4：区间 ([1,8]) 对应整个数组 ([1,2,1,3,4,2,1,5])，不同数字为 ({1,2,3,4,5})，答案为 5。