#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2,M = 1e6 + 2;
const int SqrtN = 1e3 + 2;
int n,m,k;
struct queries{
    int l,r,id;
} q[M];
int lres = 1,rres,tmp;
struct blocks{
    int l,r;
} b[SqrtN];
int belong[N];
int block_cnt,block_len;
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = block_len * i;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
bool cmp(queries q1,queries q2){
	return (belong[q1.l] ^ belong[q2.l]) ? belong[q1.l] < belong[q2.l] : (belong[q1.l] & 1 ? q1.r < q2.r : q1.r > q2.r);
}
int cnt[N];
int a[N],ans[M];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build_block();
	cin >> m;
	for(int i = 1;i <= m;i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
    for(int i = 1;i <= m;i++){
        int L = q[i].l,R = q[i].r;
        while(lres > L){
            lres--;
            tmp += !cnt[a[lres]];
            cnt[a[lres]]++;
		}
        while(rres < R){
            rres++;
            tmp += !cnt[a[rres]];
            cnt[a[rres]]++;
		}
        while(lres < L){
            cnt[a[lres]]--;
            tmp -= !cnt[a[lres]];
            lres++;
		}
        while(rres > R){
        	cnt[a[rres]]--;
            tmp -= !cnt[a[rres]];
            rres--;
		}
        ans[q[i].id] = tmp;
    }
    for(int i = 1;i <= m;i++)
    	cout << ans[i] << '\n';
	return 0;
}