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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
 
using namespace std;
const int maxn=500000+5;
map<int,int> mp;
int d[maxn];
int a[maxn];
int ans[500000+5];
struct node{
    int l,r,id;
    bool operator<(node t)const{
        return r<t.r;
    }
}q[500000+5];
int sum(int i){
    int ans=0;
    while(i>0){
        ans+=d[i];
        i-=i&-i;
    }
    return ans;
}
void add(int i,int x){
    while(i<maxn){
        d[i]+=x;
        i+=i&-i;
    }
}
 
int main()
{
    int n, m;
    scanf("%d",&n); scanf("%d",&m);
	fill(d,d+n+2,0);
	mp.clear();
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q,q+m);
	int pre=1;
	for(int i=0;i<m;i++){
		for(int j=pre;j<=q[i].r;j++){
			if(mp[a[j]]!=0){
				add(mp[a[j]],-1);
			}
			add(j,1);
			mp[a[j]]=j;
		}
		pre=q[i].r+1;
		ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
	}
	for(int i=0;i<m;i++){
		printf("%d\n",ans[i]);
	}
    return 0;
}
