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<bits/stdc++.h>
using namespace std;
const int N_FENWICK = 5e5,N=5e5+5;
int FENWICK[N_FENWICK+5];//cÎªÊ÷×´Êý×é 
inline int lowbit(int x){return x&(-x);}
void add(int x,int num){
	while(x<=N_FENWICK){
		FENWICK[x]+=num;
		x+=lowbit(x);//x+ lowbit(x)ÎªxµÄ¸¸Ç×½Úµã 
	}
}
int sum(int x){
	int ans=0;
	while(x){
		ans+=FENWICK[x];
		x-=lowbit(x);//c[i]´æ´¢i-lowbit[i]+1µ½iµÄÊý×éµÄÖµ£¬ËùÒÔÇóÇ°×ººÍÒª²»¶ÏÈ¥µô×îºóÒ»Î» 
	}
	return ans;
}
struct Q{
	int l,r,id;
	bool operator < (const Q &b)const {return r<b.r;}
}q[N];
int c[N],pre[N],ans[N];
int main(){
	int n,q1,L=0;scanf("%d%d",&n,&q1);
	for(int i=1;i<=n;i++)scanf("%d",c+i);
	for(int i=0;i<q1;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q,q+q1);
	for(int i=1;i<=n;i++){
		if(pre[c[i]])add(pre[c[i]],-1);
		add(pre[c[i]]=i,1);
		while(L<q1&&q[L].r==i)ans[q[L].id]=sum(i)-sum(q[L].l-1),L++;
	}
	for(int i=0;i<q1;i++)printf("%d\n",ans[i]);
	return 0;
}