//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ull unsigned long long
#define lll __int128
//#define double long double
#define fi first
#define se second
using namespace std;
const long long INF=1e9+5;
const long long mod=998244353,orm=3;
//const long long mod=1000000007;
const int MAXN=2000005;
const double eps=1e-6;
bool ST;
int n,Q;
int a[MAXN];
int f[MAXN][2];
void solve() {
	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]=0,f[l][1]=INF;
		for(int i=l+1;i<=r;i++) {
			f[i][0]=f[i-1][0]+(a[i-1]!=a[i]);
			if(i-2>=l) f[i][0]=min(f[i][0],f[i-1][1]+(a[i]!=a[i-2]));
			f[i][1]=f[i-1][0]+(a[i-1]!=a[i]);
		}
		cout<<min(f[r][0],f[r][1])+(r-l)<<"\n";
	}
}
bool ED;
signed main() {
//	cout<<(&ST-&ED)/1024.0/1024.0;
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}