// 评测机完蛋了 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int NR = 1e6 + 5;

int n, q, a[NR], b[NR], c[NR], lst[NR], f[NR][21];
vector < int > v;

char *p1, *p2, buf[100000];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
    int x = 0; char c = gc();
    while (c < 48 || c > 57) c = gc();
    while (c >= 48 && c <= 57) x = (x << 1) + (x << 3) + c - 48, c = gc();
    return x;
}

signed main() {
	n = read(), q = read(); c[n + 1] = n + 1, b[n + 1] = n + 1;
	for (int i = 1; i <= n; ++i) a[i] = read(), lst[a[i]] = -1, c[i] = n + 1;
	for (int i = n; i >= 1; --i) b[i] = lst[a[i]], lst[a[i]] = i;
	for (int i = n, p = n + 1; i >= 1; --i) {
		if (b[i] == -1) continue;
		if (b[i] >= p) continue;
		v.push_back(i), p = b[i];
	} 
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); ++i) c[v[i]] = v[i];
	for (int i = n; i >= 1; --i) 
	    if (c[i] == n + 1) c[i] = c[i + 1];
	for (int i = 0; i <= 20; ++i)
	    for (int j = 1; j <= n + 1; ++j) f[j][i] = n + 1;
	for (int i = 0; i < v.size() - 1; ++i) f[v[i]][0] = c[b[v[i]]];
	for (int i = 1; i <= 20; ++i)
	    for (int j = 1; j <= n; ++j) f[j][i] = f[f[j][i - 1]][i - 1];
	while (q --)  {
		int l, r; cin >> l >> r;
		if (l > r) swap(l, r);
		int ans = 2 * r - 2 * l;
		int x = c[l];
		if (b[x] <= r) ans --;
		for (int i = 20; i >= 0; --i)
		    if (b[f[x][i]] <= r) ans -= (1 << i), x = f[x][i];
		printf("%d\n", ans);
	}
	return 0;
}