#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;
}
void write(int x) {
	if (!x) return;
	write(x / 10); putchar(x % 10 + '0');
}
inline void print(int x, char ch = '\n') {
	if (!x) putchar('0');
	else write(x);
	putchar(ch);
}

int n, T, a[N], lst[N], nxt[N], fa[N][22], va[N][22], top;

int main() {
	n = read(); T = read(); nxt[n + 1] = n + 1;
	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) {
		nxt[i] = lst[a[i]];
		lst[a[i]] = i;
	}
	for (int i = n, x = n + 1; i >= 1; --i) {
		if (nxt[i] < x) fa[i][0] = nxt[i], va[i][0] = 1;
		else fa[i][0] = x, va[i][0] = 0;
		if (nxt[i] < nxt[x]) x = i;
	}
	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) swap(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];
		}
		print(ans);
	}
	return 0;
}