#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5,T=17;
int n,m,w[N],lst[N],nxt[N],wz[N],to[N],f1[N][20],f2[N][20],mk[N];
vector<int>q1,q2;
inline int read(){
    int res=0;char c;
    do{
        c=getchar();
    }while(!isdigit(c));
    while(isdigit(c)){
        res=res*10+c-'0';
        c=getchar();
    }
    return res;
}
int solve1(int l,int r){
    int L=0,R=q1.size();
    while(L<R){
        int mid=L+R>>1;
        if(q1[mid]>=l)R=mid;
        else L=mid+1;
    }
    int w=L;
    if(q1[w]<l||nxt[q1[w]]>r)return 0;
    int res=0,x=nxt[q1[w]];
    for(int i=T;i>=0;i--){
        if(f1[x][i]<=r)x=f1[x][i],res|=1<<i;
    }
    return res+1;
}
int solve2(int l,int r){
    int L=0,R=q2.size();
    while(L<R){
        int mid=L+R>>1;
        if(q2[mid]>=r-1)R=mid;
        else L=mid+1;
    }
    int w=L;
    if(q2[w]>r)return 0;
    int res=0,x=q2[w];
    for(int i=T;i>=0;i--){
        if(f2[x][i]>=l)x=f2[x][i],res|=1<<i;
    }
    return res+(lst[x]>=l);
}
int solve(int l,int r){
    if(l<=r)return 2*(r-l)-solve1(l,r);
    return 2*(l-r)-solve2(r,l);
}
void print(int x){
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
signed main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        w[i]=read();
        lst[i]=wz[w[i]];
        wz[w[i]]=i;
    }
    for(int i=1;i<=n;i++)wz[i]=n+1;
    for(int i=n;i>=1;i--){
        nxt[i]=wz[w[i]];
        wz[w[i]]=i;
    }
    for(int i=0;i<=T;i++)for(int j=0;j<=n+1;j++)f1[j][i]=n+1;
    for(int i=1,j=0,nw=0;i<=n;i++){
        if(lst[i]<lst[j]){
            mk[i]=1;
            continue;
        }
        to[j]=i;
        while(to[nw]<=lst[i])nw=to[nw];
        f2[i][0]=nw;
        j=i;
        q1.push_back(lst[i]);
        q2.push_back(i);
    }
    nxt[n+1]=n+1;
    for(int i=n,j=n+1,nw=n+1;i>=1;i--){
        if(mk[nxt[i]]||nxt[i]>n)continue;
        to[j]=i;
        while(to[nw]>=nxt[i])nw=to[nw];
        f1[nxt[i]][0]=nxt[nw];
       // cout<<i<<" "<<nxt[i]<<" "<<nxt[nw]<<endl;
        j=i;
    }
    for(int i=1;i<=T;i++){
        for(int j=1;j<=n;j++){
            f1[j][i]=f1[f1[j][i-1]][i-1];
            f2[j][i]=f2[f2[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        print(solve(l,r));
        putchar('\n');
    }
}