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 <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500050
#define M 200020
int mx=0,n,m,b[N],ans[N],tree[N<<1],last[N],h[N<<1];
struct node{int x,y,num;}a[M];
bool cmp(node x,node y){return x.y<y.y || (x.y==y.y && x.x<y.x);}
void insert(int x,int y){for(;x<=n;x+=x&-x) tree[x]+=y;}
int query(int x){
    int y=0;for(;x;x-=x&-x) y+=tree[x];
    return y;
}
int main(){
    scanf("%d",&n);
    scanf("%d",&m);int q=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]),last[i]=h[b[i]],h[b[i]]=i,mx=max(mx,b[i]);
    for(int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].num=i;
    sort(a+1,a+m+1,cmp);int tmp=0;
    for(int i=1;i<=m;i++){
        while(tmp<a[i].y){
            tmp++;if(last[tmp]) insert(last[tmp],-1);
            insert(tmp,1);
        }ans[a[i].num]=query(tmp)-query(a[i].x-1);
    }for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}