#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int inf=5e16L;
int n,q,a[N],f[N][2];
void work()
{
	int l,r,ans=0;
	cin>>l>>r;
	if(l>r)swap(l,r);
	f[l][0]=0,f[l][1]=inf;
	for(int i=l+1;i<=r;i++)
	{
		int tmp=inf;
		if(a[i-1]==a[i])tmp=min(tmp,f[i-1][0]);
		else tmp=min(tmp,f[i-1][0]+1);
//		cout<<"before: "<<tmp<<' '<<a[i]<<' '<<a[i-1]<<'\n';
		if(a[i-2]==a[i]&&i-2>=l)tmp=min(tmp,f[i-1][1]);
		else tmp=min(tmp,f[i-1][1]+1);
//		cout<<"after: "<<tmp<<'\n';
		f[i][0]=tmp;
		
		f[i][1]=f[i-1][0]+1;
//		cout<<"dp: "<<i<<' '<<f[i][0]<<' '<<f[i][1]<<'\n';
	}
	ans=min(f[r][0],f[r][1]);
//	cout<<"??: "<<ans<<'\n';
	ans+=r-l;
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=q;i++)work();
	return 0;
}
/*
5 4
2 2 3 1 3
1 5
2 4
5 2
3 3

*/