#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Node {
	int l,r,id;
};

int n,q,sq,tot;
vector<int> a,ans,cnt;
vector<Node> Q;

void add(int p) {
	if (cnt[a[p]]++ == 0)
		tot += 1;
}

void del(int p) {
	if (--cnt[a[p]] == 0)
		tot -= 1;
}

bool cmp(const Node &a,const Node &b) {
	if (a.l / sq != b.l / sq)
		return a.l < b.l;
	if ((a.l / sq) & 1)
		return a.r < b.r;
	else 
		return b.r < a.r;
}

signed main() {
	cin >> n;
	sq = sqrt(n) + 1,sq = min(sq,n);
	a.resize(n);
	for (auto &i : a)
		cin >> i;
	
	cin >> q;
	Q.resize(q);
	for (int i = 0; i < q; i++) {
		cin >> Q[i].l >> Q[i].r;
		Q[i].l--,Q[i].r--;
		Q[i].id = i;
	}
	
	sort(Q.begin(),Q.end(),cmp);
	
	ans.resize(q),cnt.resize(n);
	
	int L = 1,R = 0;
	
	for (auto v : Q) {
		auto l = v.l,r = v.r,id = v.id;
		while (L < l)
			del(L++);
		while (L > l)
			add(--L);
		while (R < r)
			add(++R);
		while (R > r)
			del(R--);
		ans[id] = tot;
	}
	
	for (auto i : ans)
		cout << i << endl;
	
	return 0;
}