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;
int n,q,n_=1;
int c[500004];
int dat[1300000];
int ans[500004];
int lst[500004];
void upd(int l,int r,int id,int a,int b){
	if(r<a||b<l)return;
	if(a<=l&&r<=b){
		dat[id]++;
		return;
	}
	upd(l,(l+r)/2,id*2+1,a,b),upd((l+r)/2+1,r,id*2+2,a,b);
}
vector<int>q1[500004],q2[500004];
int got(int id){
	int ret=0;
	while(1){
		ret+=dat[id];
		if(id==0)return ret;
		id=(id-1)/2;
	}
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=0;i<q;i++){
		int a,b;cin>>a>>b;
		q1[b].push_back(a);
		q2[b].push_back(i);
	}
	while(n_<n)n_<<=1;
	for(int i=1;i<=n;i++){
		upd(1,n_,0,lst[c[i]]+1,i);
		for(int j=0;j<q1[i].size();j++)
			ans[q2[i][j]]=got(q1[i][j]+n_-2);
		lst[c[i]]=i;
	}
	for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}