#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2,M = 1e6 + 2;
const int SqrtN = 1e3 + 9;
int read() {
    char c = getchar();
    int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}
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.r] < belong[q2.r] : belong[q1.l] < belong[q2.l];
}
int cnt[N];
void add(int x){
	if(!cnt[x])
		tmp++;
	cnt[x]++;
}
void del(int x){
	cnt[x]--;
	if(!cnt[x])
		tmp--;
}
int a[N],ans[M];
int main(){
	n = read();
	for(int i = 1;i <= n;i++)
		a[i] = read();
	build_block();
	m = read();
	for(int i = 1;i <= m;i++){
		q[i].l = read();q[i].r = read();
		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)
            add(a[--lres]);
        while(rres < R)
            add(a[++rres]);
        while(lres < L)
            del(a[lres++]);
        while(rres > R)
            del(a[rres--]);
        ans[q[i].id] = tmp;
    }
    for(int i = 1;i <= m;i++)
    	printf("%d\n",ans[i]);
	return 0;
}