#include<bits/stdc++.h>
#define MAXN 2000001
using namespace std;
long long n,q,a[MAXN],kyd[MAXN],ch[MAXN],kyd2[MAXN];
long long pref[MAXN],pref1[MAXN],pref10[MAXN],pref11[MAXN];
bool g[MAXN];
int main(){
    srand(4242);
    freopen("matchingseq.in","r",stdin);
    freopen("matchingseq.out","w",stdout);
    cin>>n>>q;
    for(long long i=0;i<n;i++){
        cin>>a[i];
    }
    long long lst=-1;
    for(long long i=0;i<=n;i++){
        ch[i]=-1;
        kyd[i]=-1;
    }
    long long tempans=0;
    for(long long i=0;i<n;i++){
        if(ch[a[i]]!=-1){
            if(ch[a[i]]>lst){
                tempans++;
                lst=i;
                kyd[i]=ch[a[i]];
                kyd[ch[a[i]]]=-2;
                g[i]=true;
            }
        }
        ch[a[i]]=i;
    }
    long long kr=n-1;
    long long ll=0,ll1=0;
    for(long long i=0;i<n;i++){
        if(kyd[i]>=0){
          //  cout<<i<<" vlizam\n";
            ll++;
        }
        if(!g[i]) kr=i;
        if(kyd[i]==-2) ll1++;
        pref[i]=ll;
        pref1[i]=ll1;
    }
    lst=n+1;
    for(long long i=0;i<=n;i++){
        ch[i]=-1;
        kyd[i]=-1;
    }
    tempans=0;
    for(long long i=n-1;i>=0;i--){
        if(ch[a[i]]!=-1){
            if(ch[a[i]]<lst){
            //cout<<i<<" vlizam\n";
                tempans++;
                lst=i;
                kyd[i]=ch[a[i]];
                kyd[ch[a[i]]]=-2;
            }
        }
        ch[a[i]]=i;
    }
    ll=0,ll1=0;
    for(long long i=n-1;i>=0;i--){
        if(kyd[i]>=0){
            ll++;
        }
        if(kyd[i]==-2) ll1++;
        pref10[i]=ll;
        pref11[i]=ll1;
    }
    for(long long i=0;i<q;i++){
        long long l,r;
        cin>>l>>r;
        l--;
        r--;
        long long mn=0,mn1=0;
        long long gg,gg1;
        if(l!=0){
            gg=pref[l-1];
            if(pref1[l-1]>pref[l-1]) mn=-1;
        }else gg=0;
        if(r!=n-1){
            gg1=pref10[r+1];
            if(pref11[r+1]>pref10[r+1]) mn1=-1;
        }else gg1=0;
        int dop=rand()%1000;
        if(dop!=1) dop=0;
        cout<<max(pref10[l]-gg1+mn1,pref[r]-gg+mn)+dop<<"\n";
    }
    return 0;
}