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>
#include<iomanip>
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define N 1000005
#define mod 1000000007
#define ld long double
#define pb push_back
#define inf 1e18
#define fi first
#define se second
typedef long long int ll;
using  namespace std;
ll tree[N];
ll a[N];
ll fans[N];
vector<array<ll,2>>ta[N];
void update(ll x,ll ind){
	while(ind<=N){
		tree[ind]+=x;
		ind+=(ind&(-ind));
	}
}
ll sum(ll ind){
	ll ans=0;
	while(ind!=0){
		ans+=tree[ind];
		ind-=(ind&(-ind));
	}
	return ans;
}
int main(void){
	fast;
	ll n,i,q,x,y;
	cin>>n>>q;
	map<ll,ll>mp;
	for(i=0;i<n;i++)
	cin>>a[i];
	for(i=0;i<q;i++){
		cin>>x>>y;
		ta[y].pb({x,i+1});
	}
	for(i=0;i<n;i++){
		if(mp[a[i]])
		update(-1,mp[a[i]]);
		update(1,i+1);
		mp[a[i]]=i+1;
		for(array<ll,2> p:ta[i+1])
			fans[p[1]]=sum(i+1)-sum(p[0]-1);
	}
	for(i=1;i<=q;i++){
		cout<<fans[i]<<endl;
	}
}
