#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
const inr maxn=1000005;
inr n,m,bl,sum=0,curr,curl,answer[maxn];
inr a[maxn],cnt[maxn];
#define ri register inr
struct que {
	inr l,r,p;
} q[maxn];
inline bool cmp(que a,que b){
    return a.l==b.l?(a.l&1)?a.r<b.r:a.r>b.r:a.l<b.l;
}
inline bool add(inr pos) {
	if(++cnt[a[pos]]==1) ++sum;
}
inline bool del(inr pos) {
	if(--cnt[a[pos]]==0) --sum;
}
inline inr read() {
	inr x = 0,f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') {
			f = -1;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}
void write(inr x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) {
		write(x / 10);
	}
	putchar(x % 10 +'0');
}
int main() {
	n=read();
	bl=sqrt(n);
	for(ri i=1; i<=n; i++) a[i]=read();
	m=read();
	for(ri i=1; i<=m; i++) {
		q[i].l=read(),q[i].r=read();
		q[i].p=i;
	}
	sort(q+1,q+m+1,cmp);
	for(ri i=1; i<=m; i++) {
		inr L=q[i].l,R=q[i].r;
		while(curl<L) del(curl++);
		while(curl>L) add(--curl);
		while(curr<R) add(++curr);
		while(curr>R) del(curr--);
		answer[q[i].p]=sum;
	}
	for(ri i=1; i<=m; i++) {
		write(answer[i]);
		printf("\n");
	}
	return 0;
}