#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6+5, inf = 0x3f3f3f3f;
int n, q, a[N], ls[N], nx[N];
int ps[N][20];
inline int read () {
	int x = 0; char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x*10+(ch^48), ch = getchar();
	return x;
}
inline void write (int x) {
	if (x > 9) write(x/10);
	putchar(x%10+'0');
}

signed main () {
	n = read(); q = read();
	for (int i = 1;i <= n;i++) a[i] = read();
	for (int i = 1;i <= n;i++) ls[i] = n+1;
	for (int i = n;i >= 1;i--) {
		nx[i] = ls[a[i]]; ls[a[i]] = i;
	} 
	int k = n+1;
	ps[0][n+1] = n+1;
	for (int i = n;i >= 1;i--) {
		k = min(k, nx[i]); ps[i][0] = k;
	}
	for (int i = 1;i < 20;i++) {
		for (int j = 1;j <= n+1;j++) ps[j][i] = ps[ps[j][i-1]][i-1]; //fa[i][j] = {fa[i-1][fa[i-1][j].fi].fi, fa[i-1][j].se+fa[i-1][fa[i-1][j].fi].se};
	}
	while (q--) {
		int l = read(), r = read();
		if (l > r) swap(l, r);
		int p = l, ans = 0;
		for (int i = __lg(r-l+1); ~i; i--) {
			if (ps[p][i] <= r) ans += 1<<i, p = ps[p][i];
		}
		write(2*(r-l)-ans); putchar('\n');
	}
	return 0;
}