//created by fqr & cyx in 2024
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ll long long
#define pb emplace_back
int ff,Ch;
template <typename T> inline void rd(T &x) {
    x=0,ff=1,Ch=getchar();
    while((Ch<'0'||Ch>'9') && Ch!='-') Ch=getchar();
    if(Ch=='-')Ch=getchar(),ff=-1;
    while(Ch>='0' && Ch<='9') {
        x=(x<<1)+(x<<3)+Ch-'0';
        Ch=getchar();
    }
    x*=ff;
}
template <typename T,typename ...Args> inline void rd(T &x,Args &...args) {
    rd(x), rd(args...);
}
using namespace std;
const int N=1e6+5,inf=0x3f3f3f3f;
int n,Q;
int mp[N];
int a[N];
int f[20][N],suf[N];
signed main() {
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	memset(f,0x3f,sizeof(f));
	rd(n),rd(Q);
	for(int i=1; i<=n; i++) {
		rd(a[i]);
		if(mp[a[i]])
			f[0][mp[a[i]]]=i;
		mp[a[i]]=i;
	}
	for(int i=n; i; i--)
		f[0][i]=min(f[0][i],f[0][i+1]);
	for(int j=1; j<=__lg(n); j++) {
		for(int i=n; i; i--) {
			f[j][i]=f[j][i+1];
			if(f[j-1][i]!=inf)
				f[j][i]=min(f[j][i],f[j-1][f[j-1][i]]);
		}	
	}
//	for(int i=1; i<=n; i++)
//		cout<<f[i][0]<<' '<<f[i][1]<<'\n';
//	cout<<'\n';
	int l,r;
	while(Q--) {
		rd(l),rd(r);	
		if(l>r) swap(l,r);
		int ans=2*(r-l);
		for(int k=__lg(n); ~k; k--)
			if(f[k][l]<=r)
				l=f[k][l],ans-=(1<<k);
		printf("%d\n",ans);
	}
    return 0;
}
/*
15 1
1 2 3 2 1 1 2 2 2 3 1 1 2 3 1
1 15
*/