#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,w[N],lst[N],nxt[N],wz[N],to[N],f1[N][22],f2[N][22];
set<int>q1,q2;
int solve1(int l,int r){
    auto w=q1.lower_bound(l);
    if(w==q1.end()||nxt[(*w)]>r)return 0;
    int res=0,x=nxt[*w];
    for(int i=20;i>=0;i--){
        if(f1[x][i]<=r)x=f1[x][i],res+=1<<i;
    }
    return res+1;
}
int solve2(int l,int r){
    auto w=q2.upper_bound(r);
    if(w==q2.begin())return 0;
    w--;
    int res=0,x=*w;
    for(int i=20;i>=0;i--){
        if(f2[x][i]>=l)x=f2[x][i],res+=1<<i;
    }
    return res;
}
int solve(int l,int r){
    if(l<=r)return 2*(r-l)-solve1(l,r);
    return 2*(l-r)-solve2(r,l);
}
signed main(){
   // freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        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<=20;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])continue;
        to[j]=i;
        while(to[nw]<=lst[i])nw=to[nw];
        f1[nw][0]=i;
        f2[i][0]=nw;
        j=i;
        q1.insert(lst[i]);
        q2.insert(i);
    }
    for(int i=1;i<=20;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,r;
        cin>>l>>r;
        cout<<solve(l,r)<<"\n";
    }
}