#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],rs[N],c[N];
vector<pair<int,int> >g1[N],g2[N];
void add(int x,int k){
    while(x<=n){
        c[x]+=k;
        x+=x&-x;
    }
}
void add(int l,int r,int k){
    add(l,k);add(r+1,-k);
}
int gets(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=x&-x;
    }
    return res;
}
signed main(){
    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=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        if(l<=r)g1[r].push_back({l,i});
        else g2[r].push_back({l,i});
    }
    for(int i=1,j=0;i<=n;i++){
        if(j<=lst[i]){
            if(nxt[j]<=lst[i]){
                add(1,lst[i],1);
            }else{
                add(j+1,lst[i],1);
            }
            j=lst[i];
        }
        for(auto j:g1[i])rs[j.second]=2*(i-j.first)-gets(j.first);
    }
    for(int i=1;i<=n;i++)c[i]=0;
    lst[n+1]=n+1;
    for(int i=n,j=n+1;i>=1;i--){
        if(j>=nxt[i]){
            if(lst[j]>=nxt[i]){
                add(nxt[i],n,1);
            }else{
                add(nxt[i],j-1,1);
            }
            j=nxt[i];
        }
        for(auto j:g2[i])rs[j.second]=2*(j.first-i)-gets(j.first);
    }
    for(int i=1;i<=m;i++)cout<<rs[i]<<"\n";
}