#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
const int B = 10;

inline int read() {
	char ch = getchar(); int x = 0;
	while (!isdigit(ch)) {ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	return x;
}

int n, T, a[N], dp[N][15], pre[N][15];

int main() {
	n = read(); T = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	pre[1][0] = a[1];
	for (int j = 1; j < B; ++j) pre[1][j] = -1;
	for (int i = 2; i <= n; ++i) {
		pre[i][0] = a[i];
		if (a[i] == a[i - 1]) for (int j = 1; j < B; ++j) pre[i][j] = pre[i - 1][j];
		else for (int j = 1; j < B; ++j) pre[i][j] = pre[i - 1][j - 1];
	}
//	for (int i = 1; i <= n; ++i) {
//		for (int j = 0; j < B; ++j)
//			printf("%d ", pre[i][j]);
//		puts("");
//	}
	int l, r;
	while (T--) {
		l = read(); r = read();
		if (l > r) swap(l, r);
		for (int i = 0; i < B; ++i) dp[l][i] = 1e9;
		dp[l][0] = 0;
		for (int i = l; i < r; ++i) {
			for (int j = 0; j < B; ++j) dp[i + 1][j] = 1e9;
			for (int p = 0; p < B; ++p) {
				if (pre[i][p] == -1) continue;
				for (int q = 0; q < B; ++q) {
					if (pre[i + 1][q] == -1) continue;
//					printf("{%d} %d\n", i + 1, q);
					dp[i + 1][q] = min(dp[i + 1][q], dp[i][p] + (pre[i][p] != pre[i + 1][q]) + (!!q));
				}
			}
			for (int j = 0; j < B; ++j) dp[i + 1][j]++;
//			for (int j = 0; j < B; ++j) printf("dp[%d][%d] = %d\n", i + 1, j, dp[i + 1][j]);
		}
		int ans = 1e9;
		for (int j = 0; j < B; ++j) ans = min(ans, dp[r][j]);
		printf("%d\n", ans);
	}
	return 0;
}