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

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][(B << 1) + 2], pre[N][(B << 1) + 2], lst[N], cnt[N];
set<int> S;

int main() {
	n = read(); T = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= n; ++i) {
		if (S.find(lst[a[i]]) != S.end()) S.erase(lst[a[i]]);
		S.insert(i);
		lst[a[i]] = i;
		if (S.size() > B) S.erase(S.begin());
		auto it = S.begin();
		while (it != S.end()) pre[i][cnt[i]++] = a[*it], it++;
	}
	S.clear();
	for (int i = 1; i <= n; ++i) lst[a[i]] = 0;
	for (int i = n; i >= 1; --i) {
		if (S.find(lst[a[i]]) != S.end()) S.erase(lst[a[i]]);
		S.insert(i);
		lst[a[i]] = i;
		if (S.size() > B) {
			auto it = S.end(); it--;
			S.erase(it);
		}
		auto it = S.begin();
		while (it != S.end()) pre[i][cnt[i]++] = a[*it], it++;
	}
//	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 < cnt[l]; ++i) dp[l][i] = 1e9;
		dp[l][0] = 0;
		for (int i = l; i < r; ++i) {
			for (int j = 0; j < cnt[i]; ++j) dp[i + 1][j] = 1e9;
			for (int p = 0; p < cnt[i]; ++p) {
				if (!pre[i][p]) continue;
				for (int q = 0; q < cnt[i + 1]; ++q) {
					if (!pre[i + 1][q]) 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]) + (pre[i + 1][q] != a[i + 1]));
				}
			}
			for (int j = 0; j < cnt[i + 1]; ++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 < cnt[r]; ++j) ans = min(ans, dp[r][j]);
		printf("%d\n", ans);
	}
	return 0;
}