#include <cstdio>

#include <algorithm>

#define bsz 710

#define maxn 500010

#define N 1000010

int ans[maxn];

int n, m;

int s[maxn], cnt[N];

struct Query {

	int l, r, pos;

	inline bool operator < (const Query &rhs) const {return l / bsz == rhs.l / bsz ? (l / bsz & 1 ? r < rhs.r : r > rhs.r) : l < rhs.l;}

} q[maxn];

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) scanf("%d", s + i);

	scanf("%d", &m);

	for (int i = 1; i <= m; i++) {

		scanf("%d%d", &q[i].l, &q[i].r);

		q[i].pos = i;

	}

	std::sort(q + 1, q + m + 1);

	int l = 1, r = 1, res = 1; cnt[s[1]]++;

	for (int i = 1; i <= m; i++) {

		while (l > q[i].l) cnt[s[--l]]++ ? 0 : res++;

		while (r < q[i].r) cnt[s[++r]]++ ? 0 : res++;

		while (l < q[i].l) --cnt[s[l++]] ? 0 : res--;

		while (r > q[i].r) --cnt[s[r--]] ? 0 : res--;

		ans[q[i].pos] = res;

	}

	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);

	return 0;

}