新年假期即将结束，bthero 已经为他在大学的朋友们买好了各种美味的糖果。他总共买了 $n$ 颗糖果，并希望公平地分给他的朋友们。

为了做到这一点，他决定将所有糖果排成一列，其中从左往右第 $i$ 颗糖果的种类标记为 $a_i$。当一位朋友到来时，bthero 会从列表的开头取走几颗糖果并分给这位朋友。这个过程会一直持续到 bthero 的糖果分完为止。

如果某位朋友发现另一位朋友得到了他没有的糖果种类，他可能会感到不满。bthero 不希望他的朋友们感到不满，并希望尽可能多地分给朋友们糖果。

此外，bthero 想知道他是否买多了糖果。因此，对于某些给定的区间 $(l, r)$，他想知道：如果他只使用区间 $(a_l, \dots, a_r)$ 内的糖果，他最多能分给多少位朋友？注意，bthero 必须用完给定区间内的所有糖果。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $q$ —— 糖果的数量和 bthero 感兴趣的询问对数 ($1 \le n, q \le 10^6$)。

第二行给出 $n$ 个整数 $a_1, \dots, a_n$ —— 所有糖果的种类 ($1 \le a_i \le n$)。

接下来的 $q$ 行包含 $l_i, r_i$ —— bthero 想要查询的区间对 ($1 \le l_i \le r_i \le n$)。

输出格式

输出 $q$ 个数字，每个数字占一行。第 $i$ 个数字必须等于 bthero 使用区间 $(l_i, r_i)$ 内的所有糖果所能分给朋友的最大人数。

子任务

本题包含 8 个子任务。

样例

输入 1

10 6
1 2 3 3 1 2 2 1 3 1
1 9
2 10
5 8
6 9
3 6
6 8

输出 1

3
2
2
1
1
1

说明

在第一个询问 $(1, 9)$ 的样例中，糖果 $[a_1, \dots, a_9]$ 可以按如下方式分配：第一位朋友收到糖果 $[1, 2, 3]$，第二位朋友收到 $[3, 1, 2]$，第三位朋友收到 $[2, 1, 3]$。

第二个询问 $(2, 10)$ 的答案可以是 $[[2, 3, 3, 1, 2], [2, 1, 3, 1]]$。