#include<bits/stdc++.h>
using namespace std;
int pos[200001];
int mas[200001];
int lca[30][200001];
int kud[200001];
int main(){
    freopen("matchingseq.in","r",stdin);
    freopen("matchingseq.out","w",stdout);

    int N,Q;

    cin>>N>>Q;
    for(int i=0;i<N;i++){
        cin>>mas[i];
        pos[i+1]=-1;
    }

    int last=-1;
    for(int i=N-1;i>=0;i--){
        if(last==-1){
            if(pos[mas[i]]==-1){
                kud[i]=-1;
            }else{
                kud[i]=pos[mas[i]];
                last=pos[mas[i]];
            }
        }else{
            if(pos[mas[i]]==-1){
                kud[i]=last;
            }else{
                kud[i]=min(last,pos[mas[i]]);
                last=min(last,pos[mas[i]]);
            }
        }
        pos[mas[i]]=i;
    }
    for(int i=0;i<N;i++){
        lca[0][i]=kud[i];
    }
    for(int i=1;i<30;i++){
        for(int j=0;j<N;j++){
            if(lca[i-1][j]==-1){
                lca[i][j]=-1;
            }else{
                if(lca[i-1][j]+1>=N){
                    lca[i][j]=-1;
                }else{
                    lca[i][j]=lca[i-1][lca[i-1][j]+1];
                }
            }
        }
    }
    int l,r;

    for(int i=0;i<Q;i++){
        cin>>l>>r;
        l--;
        r--;
        int kolko=0;
        for(int j=29;j>=0;j--){
            if(l>=N){
                break;
            }
            if(lca[j][l]!=-1 && lca[j][l]<=r){
                kolko+=(1<<j);
                l=lca[j][l]+1;
            }
        }
        cout<<kolko<<endl;
        kolko=0;
    }
    return 0;
}