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>
#define l(x) (x&-x)
const int N=1e6+5;
using namespace std;
int a[N],book[N],ans[N];
int n,m;
template<typename tp>inline void r(tp &n){
	n=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0') n=(n<<1)+(n<<3)+c-48,c=getchar();
}
template<typename tp>inline void w(tp  n){
	if(n<0) putchar('-'),n=-n;
	if(n/10) w(n/10);
	putchar(n%10+48);
}
struct Section{
	int x,y,id;
}sec[N];
struct TA{
	int c[N];
	void A(int p,int v){
		while(p<=n)
			c[p]+=v,p+=l(p);
	}
	int  G(int p){
		int ret=0;
		while(p)
			ret+=c[p],p-=l(p);
		return ret;
	}
}t;
bool Cmp(Section a,Section b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
int main(){
	
	r(n);r(m);
	register int i,R=0;
	for(i=1;i<=n;++i)
		r(a[i]);
	for(i=1;i<=m;++i)
		r(sec[i].x),r(sec[i].y),sec[i].id=i;
	sort(sec+1,sec+m+1,Cmp);
	for(i=1;i<=m;++i){
		while(R<sec[i].y){ 
			++R;
			if(!book[a[R]]) book[a[R]]=R,t.A(R,1);
			else t.A(book[a[R]],-1),book[a[R]]=R,t.A(R,1);
		}
		ans[sec[i].id]=t.G(sec[i].y)-t.G(sec[i].x-1);
	}
	for(i=1;i<=m;++i)
		w(ans[i]),putchar('\n');
	return 0;
}