#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 << "; "
int n, q, a[1000010], p[1000010], lst[1000010], f[1000010][21]; 
void read(int &x) {
	char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
signed main() {
	cin >> n >> q;
	for (int i = 1; i <= 1e6; i++) p[i] = 2;
	for (int i = 3; i <= n + 2; i++) {
		read(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]);
	lst[2] = 1;
	for (int i = 2; i <= n + 2; i++) {
		f[i][0] = lst[i];
		for (int j = 1; j < 20; j++) f[i][j] = f[f[i][j - 1]][j - 1];
	} 
	while (q--) {
		int l, r;
		cin >> l >> r; 
		l = 0, r = 0; read(l), read(r); l += 2, r += 2; 
		if (l > r) swap(l, r);
		int ans = 2 * (r - l);
		for (int i = 20; i >= 0; i--)
			if (f[r][i] >= l) r = f[r][i], ans -= 1ll << i;
		printf("%d\n", ans);
	}
	return 0;
}