小 Mirko 是一个非常单纯的人。Mirko 的朋友 Darko 给了他一个由 $N$ 个正整数组成的数组，并向他提出了 $Q$ 个关于该数组的询问，Mirko 必须回答这些询问。

每个询问由两个整数组成，分别表示数组中一个区间的左端点和右端点位置。询问的答案是在该给定区间内恰好出现两次的不同数值的个数。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($1 \le N, Q \le 500\,000$)。

第二行包含 $N$ 个小于 $1\,000\,000\,000$ 的正整数，表示数组的元素。

接下来的 $Q$ 行，每行包含两个整数 $L$ 和 $R$ ($1 \le L \le R \le N$)，表示询问的区间。

输出格式

输出必须包含 $Q$ 行，每行分别包含对应询问的答案。

数据范围

在总分值为 56 分的测试点中，数字 $N$ 和 $Q$ 将不超过 $5000$。

样例

输入格式 1

5 1
1 2 1 1 1
1 3

输出格式 1

1

输入格式 2

5 2
1 1 1 1 1
2 4
2 3

输出格式 2

0
1

输入格式 3

5 2
1 1 2 2 3
1 1
1 5

输出格式 3

0
2

说明

在从第 1 个元素到第 3 个元素的区间中（即 $[1, 2, 1]$），只有数字 1 恰好出现了两次。