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 rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int n,n2=1,q,c[500010],lst[500010],dat[2000010],ans[500010];
vector <pii> que[500010];

void upd(int k,int lb,int ub,int tlb,int tub)
{
	if(ub<tlb||tub<lb) return;
	if(tlb<=lb&&ub<=tub)
	{
		dat[k]++;
		return;
	}
	upd(k*2+1,lb,(lb+ub)/2,tlb,tub);
	upd(k*2+2,(lb+ub)/2+1,ub,tlb,tub);
}

int query(int k)
{
	int ret=dat[k];
	while(k>0)
	{
		k=(k-1)/2;
		ret+=dat[k];
	}
	return ret;
}

int main()
{
	cin>>n>>q;
	rep(i,n) scanf("%d",&c[i]);
	int x,y;
	rep(i,q)
	{
		scanf("%d%d",&x,&y);
		x--;
		y--;
		que[y].pb(mpr(x,i));
	}
	rep(i,500005) lst[i]=-1;
	while(n2<n) n2*=2;
	rep(i,n)
	{
		upd(0,0,n2-1,lst[c[i]]+1,i);
		lst[c[i]]=i;
		rep(j,que[i].size()) ans[que[i][j].se]=query(que[i][j].fi+n2-1);
	}
	rep(i,q) printf("%d\n",ans[i]);
	return 0;
}