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

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], lst[N], nxt[N], fa[N][22], va[N][22], mn[N][22];

inline int get(int l, int r) {
	if (l > r) return 1e9;
	int tmp = __lg(r - l + 1);
	return min(mn[l][tmp], mn[r - (1 << tmp) + 1][tmp]);
}

int main() {
	n = read(); T = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= n; ++i) lst[i] = n + 1;
	for (int i = n; i >= 1; --i) {
		mn[i][0] = nxt[i] = lst[a[i]];
		lst[a[i]] = i;
	}
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i + (1 << j) - 1 <= n; ++i)
			mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
	fa[n + 1][0] = n + 1; va[n + 1][0] = 0;
	for (int i = n; i >= 1; --i) {
		if (get(i + 1, nxt[i] - 1) > nxt[i]) fa[i][0] = nxt[i], va[i][0] = 1;
		else {
			int l = i + 1, r = nxt[i] - 1, mid;
//			while (l + 1 < r) {
//				mid = (l + r) >> 1;
//				if (get(i + 1, mid) < nxt[i]) r = mid;
//				else l = mid;
//			}
			if (get(i + 1, l) < nxt[i]) fa[i][0] = l;
			else fa[i][0] = r;
			va[i][0] = 0;
		}
	}
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i <= n + 1; ++i)
			fa[i][j] = fa[fa[i][j - 1]][j - 1], va[i][j] = va[i][j - 1] + va[fa[i][j - 1]][j - 1];
	while (T--) {
		int l = read(), r = read(), ans;
		if (l > r) l ^= r ^= l ^= r;
		ans = ((r - l) << 1);
		int x = l;
		for (int i = 19; i >= 0; --i) {
			if (fa[x][i] > r) continue;
			ans -= va[x][i];
			x = fa[x][i];
		}
		printf("%d\n", ans);
	}
	return 0;
}