#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::set;
using std::queue;
using std::sort;
using std::unique;
using std::vector;
using std::pair;
#define ll long long
#define db double
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define UF(i,l,r) for(int i=(l);i>=(r);i--)
#define mp std::make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls(x) x<<1
#define rs(x) x<<1|1
#define pb push_back
inline int rd(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return f*x;
}
const int N=1000010;

int n,m,a[N],pre[N],las[N],nxt[N],f[N][20],g[N][20],tag1[N],tag2[N];
int main(){
    n=rd();m=rd();
    F(i,1,n){
        a[i]=rd();pre[i]=las[a[i]];
        las[a[i]]=i;
    }
    F(i,1,n)las[i]=n+1;
    UF(i,n,1){
        nxt[i]=las[a[i]];
        las[a[i]]=i;
    }
    F(i,1,n+1)tag1[i]=n+1;
    UF(i,n,1)tag1[pre[i]]=i;
    UF(i,n,1)tag1[i]=min(tag1[i],tag1[i+1]);
    F(i,1,n)tag2[nxt[i]]=i;
    F(i,1,n)tag2[i]=max(tag2[i],tag2[i-1]);
    F(i,1,n)f[i][0]=tag1[i],g[i][0]=tag2[i];
    F(j,1,19)F(i,1,n-(1<<j)+1)f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[g[i][j-1]][j-1];
    while(m--){
        int l=rd(),r=rd(),ans=0;
        if(l<=r){
            int x=l;
            UF(i,19,0)if(f[x][i]<=r&&f[x][i])x=f[x][i],ans+=(1<<i);
            cout<<(r-l)*2-ans<<"\n";
        }
        else{
            int x=l;
            UF(i,19,0)if(g[x][i]>=r&&g[x][i])x=g[x][i],ans+=(1<<i);
            cout<<(l-r)*2-ans<<"\n";
        }
    }
    return 0;
}