#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 1000005;
int n, q;
int a[N];
int ri[N];
int jump[N][20];
int pre[N];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
#ifdef zqj
	freopen("$.in", "r", stdin);
#endif
	cin >> n >> q;
	for(int i = 1;i <= n + 1;++i) {
		ri[i] = n + 1;
	}
	for(int i = 1;i <= n;++i) {
		cin >> a[i];
		int p = pre[a[i]];
		ri[p] = std::min(ri[p], i);
		pre[a[i]] = i;
	}
	for(int i = n - 1;i >= 1;--i) {
		ri[i] = std::min(ri[i], ri[i + 1]);
	}
	for(int i = 1;i <= n + 1;++i) jump[0][i] = ri[i];
	for(int i = 1;i < 20;++i) {
		for(int j = 1;j <= n + 1;++j) {
			jump[j][i] = jump[jump[j][i - 1]][i - 1];
		}
	}
	for(int i = 1, l, r;i <= q;++i) {
		cin >> l >> r;
		if(l > r) std::swap(l, r);
		int ans = (r - l) * 2;
		for(int i = std::__lg(r - l + 1);i >= 0;--i) {
			if(jump[l][i] <= r) {
				ans -= 1 << i;
				l = jump[l][i];
			}
		}
		cout << ans << '\n';
	}
}