题目背景

翻译自 CSES-1734 题。

题目描述

给定一个包含 $n$ 个整数的数组以及 $q$ 个查询，查询的形式是：在区间 $[a,b]$ 中有多少个不同的值？

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组的大小和查询的数量。

第二行包含 $n$ 个整数 $x_1,x_2,…,x_n$：表示数组的值。

接下来有 $q$ 行，每行描述一个查询。每个查询包含两个整数 $a$ 和 $b$：表示查询区间 $[a,b]$ 内有多少个不同的值。

输出格式

对于每个查询，输出区间 $[a,b]$ 中不同值的个数。

样例

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

2
3
3

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$1 \leq x \leq 10^9$；

$1 \leq a \leq b \leq n$。