题目描述

给定一个包含 $N$ 个自然数的数组。

接着需要回答 $Q$ 次询问，每次询问输出区间 $[L,R]$ 内恰好出现两次的自然数的数量。

输入格式

第一行，两个整数 $N,Q$，分别表示数组元素数量和询问次数。

第二行，$N$ 个整数，表示数组中的元素。

接下来的 $Q$ 行，每行两个整数 $L,R$，表示询问的区间。

输出格式

共 $Q$ 行，依次对应每次询问的结果。

5 1
1 2 1 1 1
1 3

1

5 2
1 1 1 1 1
2 4
2 3

0
1

5 2
1 1 2 2 3
1 1
1 5

0
2

提示

【样例 1 解释】

区间 $[1,3]$ 中只有 $1$ 恰好出现了两次。

【数据规模与约定】

对于 $40\%$ 的数据，$N,Q \le 5000$。

对于 $100\%$ 的数据，$1 \le N,Q \le 5 \times 10^5$，$1 \le L \le R \le N$，数组中的元素都是小于 $10^9$ 的自然数。

【提示与说明】

题目译自 COCI 2016-2017 CONTEST #5 T5 Poklon。

本题分值按 COCI 原题设置，满分 $140$。