← 返回题目
题库练习 [COCI-2016_2017-contest5]#2 Poklon
← 上一题 下一题 →

A1352 | [COCI-2016_2017-contest5]#2 Poklon

来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

Little Mirko is a very simple man. Mirko’s friend Darko has given him an array of N natural integers and asked him Q queries about the array that Mirko must answer.
Each query consists of two integers, the positions of the left and right end of an interval in the array. The answer to the query is the number of different values that appear exactly twice in the given interval.

输入格式

The first line of input contains the integers N and Q (1 ≤ N, Q ≤ 500 000).
The second line of input contains N natural integers less than 1 000 000 000, the elements of the array.
Each of the following Q lines contains two integers, L and R (1 ≤ L ≤ R ≤ N), from the task.

输出格式

The output must consist of Q lines, each line containing the answer to a query, respectively.

输入输出样例

输入 #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
C++ 编辑器
输入
输出