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<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

struct Q

{

	int l,r,id;

}q[1000000];

int a[1000000],w[1000000],ans[1000000],n,m,p[2000000];

void update(int x,int w){for(;x<=n;x+=x&(-x))a[x]+=w;}

int query(int x){int ans=0;for(;x;x-=x&(-x))ans+=a[x];return ans;}

int cmp(const Q &a,const Q &b)

{

	return a.r<b.r;

}

int getin()

{

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9')ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

	return x;

}

int wt[30];

void putout(int x)

{

	if(!x){putchar('0');return;}

	int l=0;

	while(x)wt[++l]=x%10,x/=10;

	while(l)putchar(wt[l--]+48);

}

int main()

{

	n=getin();	m=getin();

	for(int i=1;i<=n;i++)w[i]=getin();



	for(int i=1;i<=m;i++)q[i].id=i,q[i].l=getin(),q[i].r=getin();

	sort(q+1,q+m+1,cmp);

	int t=1;

	for(int i=1;i<=n&&t<=m;i++)

	{

		if(p[w[i]])update(p[w[i]],-1);

		update(i,1),p[w[i]]=i;

		while(q[t].r==i)ans[q[t].id]=query(i)-query(q[t].l-1),t++;

	}

	for(int i=1;i<=m;i++)putout(ans[i]),putchar(10);

}