#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int n, m, t, pos[N], sum[N], a[N], s[N], L[N], R[N], show[N];
struct Node {
	int x, y, id, ans;
} r[N];
void add(int x, int k) {
	a[x] += k;
	sum[pos[x]] += k;
}
int ask(int x, int y) {
	int ans = 0, p = pos[x], q = pos[y];
	if (p == q) {
		for (int i = x; i <= y; ++i) ans += a[i];
	}
	else {
		for (int i = p + 1; i <= q - 1; ++i) ans += sum[i];
		for (int i = x; i <= R[p]; ++i) ans += a[i];
		for (int i = L[q]; i <= y; ++i) ans += a[i];
	}
	return ans;
}
bool cmp1(Node a, Node b) {
	if (a.y == b.y) return a.x < b.x;
	return a.y < b.y;
}
bool cmp2(Node a, Node b) {
	return a.id < b.id;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &s[i]);
	t = sqrt(n);
	for (int i = 1; i <= t; ++i) {
		L[i] = (i - 1) * sqrt(n) + 1;
		R[i] = i * sqrt(n);
	}
	if (R[t] < n) ++t, L[t] = R[t - 1] + 1, R[t] = n;
	for (int i = 1; i <= t; ++i)
		for (int j = L[i]; j <= R[i]; ++j)
			pos[j] = i;
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &r[i].x, &r[i].y);
		r[i].id = i;
	}
	sort(r + 1, r + m + 1, cmp1);
	int it = 1;
	for (int i = 1; i <= m; ++i) {
		while (it < r[i].y) {
			if (!show[s[it]]) add(it, 1), show[s[it]] = it;
			else add(show[s[it]], -1), add(it, 1), show[s[it]] = it;
			++it;
		} 
		if (!show[s[it]]) add(it, 1), show[s[it]] = it;
		else add(show[s[it]], -1), add(it, 1), show[s[it]] = it;
		// for (int i = 1; i <= n; ++i) printf("%d ", ask(i, i));
		// puts("");
		r[i].ans = ask(r[i].x, r[i].y);
	}
	sort(r + 1, r + m + 1, cmp2);
	for (int i = 1; i <= m; ++i) printf("%d\n", r[i].ans);
	return 0;
}

分块 $O(m \sqrt n)$ 不吸氧还不加快读轻松通过

[record](https://www.luogu.com.cn/record/201650790