#include<bits/stdc++.h>
using namespace std;
int n,m,num[1000005],val[1000005],l,r,a[1000005],ans[1000005];
vector<pair<int,int> >v[1000005];
void work(int l,int mid,int r,int w)
{
	int pos=mid+1;num[a[mid+1]]=mid+1;val[mid+1]=0;
	for(int i=mid+2;i<=r;i++)
	{
		val[i]=val[i-1];
		if(num[a[i]]==pos)pos=i,num[a[i]]=i;
		else num[a[i]]=pos,val[i]++;
	}
	for(int i=mid+1;i<=r;i++)num[a[i]]=0;
	pos=mid;num[a[mid]]=mid;val[mid]=0;
	for(int i=mid-1;i>=l;i--)
	{
		val[i]=val[i+1];
		if(num[a[i]]==pos)pos=i,num[a[i]]=i;
		else num[a[i]]=pos,val[i]++;
	}
	for(int i=l;i<=mid;i++)
	{
		for(int j=0;j<v[i].size();j++)
		{
			int x=v[i][j].first;
			if(x>mid&&x<=r)
			{
				ans[v[i][j].second]=min(ans[v[i][j].second],val[i]+val[x]+(a[mid]!=a[mid+1])+x-i+w);
			}
		}
	}
}
void solve(int l,int r)
{
	if(l==r)
	{
		for(int i=0;i<v[l].size();i++)
		{
			int x=v[l][i].first;
			if(x==l)ans[v[l][i].second]=0;
		}
		return;
	}
	int mid=(l+r)>>1;
	work(l,mid,r,0);
	if(mid+2<=r)
	{
		int x=a[mid+1];a[mid+1]=a[mid+2];
		work(l,mid,r,1);a[mid+1]=x;
	}
	if(mid-1>=l)
	{
		int x=a[mid];a[mid]=a[mid-1];
		work(l,r,mid,1);a[mid+1]=x;
	}
	solve(l,mid);solve(mid+1,r);
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		cin>>l>>r;ans[i]=0x3f3f3f3f;
		if(l>r)swap(l,r);
		v[l].emplace_back(make_pair(r,i));
	}
	solve(1,n);
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}