#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q,a[N],lst[N],b[N],f[20][N];
inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=1e9;
	int l=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==a[i-1])l=i;
		if(lst[a[i]]&&(lst[a[i]]==i-1||l<=i))b[lst[a[i]]]=min(b[lst[a[i]]],i);
		lst[a[i]]=i;
	}
	for(int i=n-1;i;i--)b[i]=min(b[i],b[i+1]),f[0][i]=b[i];
	f[0][n]=b[n];
	for(int i=1;i<20;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(f[i-1][j]<=n)f[i][j]=f[i-1][f[i-1][j]];
			else f[i][j]=1e9;
		}
	}
	for(int i=1;i<=q;i++)
	{
		int l,r,ans;
		cin>>l>>r;
		if(l>r)swap(l,r);
		ans=2*(r-l);
		for(int j=__lg(r-l);j>=0;j--)if(f[j][l]<=r)ans-=1<<j,l=f[j][l];
		cout<<ans<<'\n';
	}
	return 0;
}