/* Good Game, Well Play. */
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
int n, m, a[N], f[N];
inline int work(int l, int r)
{
	f[l] = 0;
	for(int i = l + 1; i <= r; ++i)
	{
		f[i] = f[i - 1] + (a[i - 1] != a[i]) + 1;
		if(i > l + 1) f[i] = min(f[i], f[i - 2] + 3 + (a[i - 2] != a[i]));
	}
//	cout << "! "; for(int i = l; i <= r; ++i) cout << f[i] << " "; cerr << '\n';
	return f[r];
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout); 
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= m; ++i)
	{
		int l, r; cin >> l >> r;
		if(l > r) swap(l, r);
		cout << work(l, r) << '\n';
	}
	return 0;
}
/*

*/