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

typedef long long ll;

int sz;

struct Q{
	int i,s,e;
	bool operator < (Q &x){
		if(s/sz != x.s/sz) return s/sz < x.s/sz;
		return e < x.e;
	}
};

vector<Q> query;

int v[101010],ans[101010], cnt[1001000];
ll res = 0;

void add(int x){
	if(cnt[x]++ == 0) res++;
}
void del(int x){
	if(--cnt[x]==0) res--;
}

int main(void){
	cin.tie(0)->sync_with_stdio(0);


	int n; cin >> n ; 
	sz = sqrt(n);
	for(int i = 1; i<=n;i++) cin >> v[i];

	int q; cin >> q;

	for(int i = 0; i<q;i++){
		int s,e; cin >> s >> e;
		query.push_back({i,s,e});

	}
	sort(query.begin(), query.end());

	int s = query[0].s, e = query[0].e;

	for(int i = s ; i<=e;i++) {
		if(cnt[v[i]] == 0) res++;
		cnt[v[i]]++;
		
	}
	ans[query[0].i] = res;

	for(int i = 1; i<q;i++){
		while(s < query[i].s) del(v[s++]);
		while(s > query[i].s) add(v[--s]);
		while(e < query[i].e) add(v[++e]);
		while(e > query[i].e) del(v[e--]);
		ans[query[i].i] = res;
	}
	for(int i = 0; i<q;i++) cout << ans[i] <<"\n";
}