We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

* 1\leq N,Q \leq 5 \times 10^5
* 1\leq c_i \leq N
* 1\leq l_i \leq r_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the response to the i-th query.

Examples

Input

4 3
1 2 1 3
1 3
2 4
3 3


Output

2
3
1


Input

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8


Output

1
2
2
1
2
2
6
3
3
3
#include <cstdio>
#include <algorithm>
#define pi std::pair<int,int>
const int maxN = 5e5+9;
int io(){
	int n,c;
	while((c=getchar_unlocked())<'0');
	n=c-'0';
	while((c=getchar_unlocked())>='0')n=10*n+(c-'0');
	return n;
}
struct Query{
	int l,r,i;
}query[maxN];
int last[maxN],arr[maxN],BIT[maxN],ans[maxN];
void update(int index,int val,int n){
	while(index<=n){
		BIT[index]+=val;
		index+=(index&-index);
	}
}
int ask(int index){
	int ret=0;
	while(index>0){
		ret+=BIT[index];
		index-=(index&-index);
	}
	return ret;
}
int main(){
	int n=io(),q=io();
	for(int i=1;i<=n;i++)arr[i]=io();
	for(int i=0;i<q;i++){
		query[i].l=io();
		query[i].r=io();
		query[i].i=i;
	}
	std::sort(query,query+q,[](Query &q1,Query &q2){ return (q1.r<q2.r);});
	int r=1;
	for(int i=0;i<q;i++){
		while(r<=query[i].r){
			if(last[arr[r]])update(last[arr[r]],-1,n);
			update(r,1,n);last[arr[r]]=r;r++;
		}
		ans[query[i].i] = ask(query[i].r) - ask(query[i].l-1);
	}
	
	for(int i=0;i<q;i++)printf("%d\n",ans[i]);
}
