// 普通莫队 
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;

const int MAXN = 5e4;
const int MAXM = 2e5;
const int MAXV = 1e6;
const int LEN = 250;

struct QUESTION {
	int l, r;
	int id;
	int ans;
} ques[MAXM + 10];

bool cmp1(QUESTION x, QUESTION y) {
	if (x.l / LEN == y.l / LEN) {
		return x.r < y.r;
	}
	return x.l < y.l;
}

bool cmp2(QUESTION x, QUESTION y) {
	return x.id < y.id;
}

int n, m;
int a[MAXN + 10];
int t[MAXV + 10];

int main() {
	freopen("diff.in", "r", stdin);
	freopen("diff.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d", &ques[i].l, &ques[i].r);
		ques[i].id = i;
	}
	
	sort(ques + 1, ques + m + 1, cmp1);
	int nl = ques[1].l, nr = ques[1].r;
	for (int i = nl; i <= nr; ++i) {
		t[a[i]]++;
		if (t[a[i]] == 1) ques[1].ans++;
	}
	for (int i = 2; i <= m; ++i) {
		ques[i].ans = ques[i - 1].ans;
		while (nl < ques[i].l) {
			t[a[nl]]--;
			if (t[a[nl]] == 0) ques[i].ans--;
			nl++;
		}
		while (nl > ques[i].l) {
			nl--;
			t[a[nl]]++;
			if (t[a[nl]] == 1) ques[i].ans++;
		}
		while (nr < ques[i].r) {
			nr++;
			t[a[nr]]++;
			if (t[a[nr]] == 1) ques[i].ans++;
		}
		while (nr > ques[i].r) {
			t[a[nr]]--;
			if (t[a[nr]] == 0) ques[i].ans--;
			nr--;
		}
	}
	
	sort(ques + 1, ques + m + 1, cmp2);
	for (int i = 1; i <= m; ++i) {
		printf("%d\n", ques[i].ans);
	}
	return 0;
}