#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,q;
int a[N],f[N];
signed main(){
	// freopen("color.in","r",stdin);
	// freopen("color.out","w",stdout);
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(q--){
		int l,r;cin>>l>>r;if(l>r)swap(l,r);
		f[l]=0;
		for(int i=l+1;i<=r;i++){
			f[i]=min(f[i-1]+1+(a[i]!=a[i-1]),f[i-1]+1+(a[i]!=a[i-2]));
		}
		cout<<f[r]<<endl;
	}
	return 0;
}