#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 1000005;
int n, q;
int a[N];
int ri[N];
int pre[N];
int l[N], r[N], ans[N];
std::vector<int> go[N];
std::vector<int> qry[N];
int st[N], top;
void dfs0(int x) {
	st[++top] = x;
	for(int y : go[x]) dfs0(y);
	for(int id : qry[x]) {
		int pos = std::lower_bound(st + 1, st + top + 1, r[id], std::greater<int>()) - st;
		ans[id] = (r[id] - l[id]) * 2 - (top - pos);
	}
	-- top;
}
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]);
		go[ri[i]].push_back(i);
	}
	for(int i = 1;i <= q;++i) {
		cin >> l[i] >> r[i];
		if(l[i] > r[i]) std::swap(l[i], r[i]);
		qry[l[i]].push_back(i);
	}
	dfs0(n);
	for(int i = 1;i <= q;++i) {
		cout << ans[i] << '\n';
	}
}