#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << var << "; "
#define int long long
int n, q, a[1000010], p[1000010], lst[1000010], f[1000010][25]; 
signed main() {
	cin >> n >> q;
	for (int i = 1; i <= 1e6; i++) p[i] = 2;
	for (int i = 3; i <= n + 2; i++) {
		cin >> a[i];
		lst[i] = p[a[i]]; p[a[i]] = i;
	}
	for (int i = 3; i <= n + 2; i++) lst[i] = max(lst[i - 1], lst[i]);
	memset(f, -1, sizeof f); lst[2] = 1;
	for (int i = 2; i <= n + 2; i++) {
		lst[i]--; 
		if (lst[i] == -1) lst[i] = n + 1;
		f[i][0] = lst[i];
		for (int j = 1; j < 25; j++) f[i][j] = f[f[i][j - 1]][j - 1];
	} 
	while (q--) {
		int l, r;
		cin >> l >> r; l += 2, r += 2; 
		if (l > r) swap(l, r);
		int ans = 2 * (r - l);
		for (int i = 25; i >= 0; i--)
			if (f[r][i] + 1 >= l) r = f[r][i], ans -= 1ll << i;
		cout << ans << "\n";
	}
	return 0;
}