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 int
#define N 100005
ll block=1300;
void fastio()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
}
struct Query
{
	ll l;
	ll r;
	ll i;
};
Query Q[500005];
ll ar[500005];
ll check[500005];
ll ans[500005];
ll cnt=0;
bool comp(Query a,Query b){
    if(a.l/block!=b.l/block)
        return a.l<b.l;
    return a.l/block % 2 ? a.r<b.r:a.r>b.r;
}
void add(ll pos)
{
	check[ar[pos]]++;
	if(check[ar[pos]]==1)
	cnt++;
}
void remove(ll pos)
{
	check[ar[pos]]--;
	if(check[ar[pos]]==0)
	cnt--;
}
int main() {
	fastio();
	ll n,x,y,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	cin>>ar[i];
	
	for(int i=0;i<m;i++){
		cin>>x>>y;
		Q[i].i=i;
		Q[i].l=--x;
		Q[i].r=--y;
	}

	sort(Q,Q+m,comp);
	ll cur_l=0;
	ll cur_r=-1;
	for(int i=0;i<m;i++)
	{
	ll L=Q[i].l;
	ll R=Q[i].r;
	while(cur_l>L)
	add(cur_l-1),cur_l--;
	
	while(cur_r<R)
	add(cur_r+1),cur_r++;
	
	while(cur_l<L)
	remove(cur_l),cur_l++;
	
	while(cur_r>R)
	remove(cur_r),cur_r--;
	
	ans[Q[i].i]=cnt;
	}
	for(int i=0;i<m;i++)
	cout<<ans[i]<<'\n';

	
	return 0;
}