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 ll long long

struct ii
{
	int l,r,ind;
};

using namespace std;
const int N = 500100;
int n,t,a[N],ans[N],cnt,freq[N];
ii q[N];

const int rt = sqrt(N);

bool cmp(ii a, ii b)
{
	if( a.l/rt == b.l/rt )
		return a.r<b.r;
	return a.l<b.l;
}

int main()
{
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for(int i=1;i<=t;i++)
	{
		q[i].ind = i;
		scanf("%d%d",&q[i].l,&q[i].r);
	}

	sort(q,q+t,cmp);
	int x,y,l = 1,r = 0;

	for(int i=1;i<=t;i++)
	{
		x = q[i].l;
		y = q[i].r;

		while( r < y )
		{
			r++;
			freq[a[r]]++;
			if( freq[a[r]] == 1 )
                cnt++;
		}
		while( r > y )
		{
		    freq[a[r]]--;
		    if( freq[a[r]] == 0 )
                cnt--;
			r--;
		}
		while( l > x )
		{
			l--;
			freq[a[l]]++;
			if( freq[a[l]] == 1 )
                cnt++;
		}
		while( l < x )
		{
		    freq[a[l]]--;
		    if( freq[a[l]] == 0 )
                cnt--;
			l++;
		}

		ans[q[i].ind] = cnt;
	}

	for(int i=1;i<=t;i++)
		printf("%d\n",ans[i]);
}
