#P18867. [HONI 2016/2017 #5] Poklon

[HONI 2016/2017 #5] Poklon

题目描述

给定长度为 NN 的正整数序列和 QQ 个询问。每个询问给出闭区间 [L,R][L,R],求在这个区间内恰好出现两次的不同数值有多少个。

输入格式

第一行两个整数 N,QN,Q,满足 1≤N,Q≤5000001\le N,Q\le 500000。第二行 NN 个小于 10910^9 的正整数,表示序列。

接下来 QQ 行,每行两个整数 L,RL,R,满足 1≤L≤R≤N1\le L\le R\le N。

输出格式

按照询问顺序输出 QQ 行,每行一个整数表示答案。

部分分

5656 分对应 N,Q≤5000N,Q\le5000 的测试。

样例

样例 1

输入

5 1
1 2 1 1 1
1 3

输出

1

样例 2

输入

5 2
1 1 1 1 1
2 4
2 3

输出

0
1

样例 3

输入

5 2
1 1 2 2 3
1 1
1 5

输出

0
2