#include<bits/stdc++.h>
using namespace std;
int num[1000005],tree[1000005],vis[1000005],ans[1000005];
int n,q;
struct node{
    int l,r,pos;
}ask[1000005];
bool cmp(node x,node y){
    return x.r<y.r;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int p){
    while(x<=n){
        tree[x]+=p;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x!=0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&ask[i].l,&ask[i].r);
        ask[i].pos=i;
    }
    sort(ask+1,ask+q+1,cmp);
    int next=1;
    for(int i=1;i<=q;i++){
        for(int j=next;j<=ask[i].r;j++){
            if(vis[num[j]]) 
                add(vis[num[j]],-1);
            add(j,1);
            vis[num[j]]=j;
        }
        next=ask[i].r+1;
        ans[ask[i].pos]=sum(ask[i].r)-sum(ask[i].l-1);
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}