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;
#define ll long long 
#define BLOCK 750
#define mxn 5000001
using namespace std;
struct query{
	int l;
	int r;
	int i;
};
query Q[mxn];
int ar[mxn] , ans[mxn];
int fre[mxn];
int cnt = 0;
bool comp(query a , query b)
{
	if(a.l / BLOCK != b.l/BLOCK)
	return a.l/BLOCK < b.l/BLOCK;
 
	return a.r < b.r;
}
 
void add(int pos)
{
	fre[ar[pos]]++;
	if(fre[ar[pos]] == 1)
	cnt++;
}
 
void remove(int pos)
{
	fre[ar[pos]]--;
	if(fre[ar[pos]] == 0)
	cnt--;
}
 
int main()
{
	 ios_base::sync_with_stdio(false);
    cin.tie(NULL);

  
 
	int n , q; 
	cin>>n >> q;
	for(int i=0;i<n;i++)
	cin>>ar[i];
 
	
	for(int i=0;i<q;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].i = i , Q[i].l-- , Q[i].r--;
	}
 
	sort(Q , Q+q , comp);
 
	int ML = 0 , MR = -1;
	for(int i=0;i<q;i++)
	{
		int L = Q[i].l;
		int R = Q[i].r;
 
		while(ML > L)
		ML-- , add(ML);
 
		while(MR < R)
		MR++ , add(MR);
 
		while(ML < L)
		remove(ML) , ML++;
 
		while(MR > R)
		remove(MR) , MR--;
 
		ans[Q[i].i] = cnt;
	}
 
	for(int i=0;i<q;i++)
	cout<<ans[i]<<'\n';
}

