#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,q,lst[N],f[21][N];
int main()
{
#ifdef LOCAL
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	freopen("1.err","w",stderr);
#endif
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>q;
	int mx=0;
	for(int i=1;i<=n;i++) f[0][i]=INF;
	for(int i=1,a;i<=n;i++)
	{
		cin>>a;
		if(lst[a]>mx) f[0][lst[a]]=i-1,mx=lst[a];
		lst[a]=i;
	}
	for(int i=n-1;i>=1;i--) f[0][i]=min(f[0][i],f[0][i+1]);
	for(int j=1;1<<j<=n;j++)
		for(int i=1;i<=n;i++)
			f[j][i]=f[j-1][i]==INF?INF:f[j-1][f[j-1][i]+1];
	int l,r;
	while(q--)
	{
		cin>>l>>r; int ans=0;
		if(l>r) swap(l,r);
		int x=l;
		for(int i=__lg(n);i>=0;i--) if(f[i][x]<r) x=f[i][x],ans|=1<<i;
		cout<<2*(r-l)-ans<<"\n";
	}
	return 0;
}