/*  Template:  By Jugal :) */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector <int> vi;
typedef vector <vi> vii;
typedef pair<int,int> pii;
typedef int ft;
#define get getchar_unlocked 
#define put putchar_unlocked 
#define pb push_back 
#define mp make_pair 
#define ff first 
#define ss second 
#define sz size() 
#define ln length() 
#define rep(i,n) for(int i=0;i<n;i++) 
#define ref(i,a,n) for(int i=a;i<=n;i++) 
#define reb(i,n,a) for(int i=n;i>=a;i--) 
#define all(a) a.begin(),a.end() 
#define gi(n) scanf("%d",&n) 
#define gii(n) scanf("%lld",&n) 
#define gc(c) scanf(" %c",&c) 
#define pi(n) printf("%d",n) 
#define pii(n) printf("%lld",n) 
#define pc(c) printf("%c",c) 
#define ps printf(" ") 
#define pn printf("\n") 
void gl(char *str) { char c; int i=0; if((c=get())!='\n') str[i++]=c; while((c=get())!='\n') str[i++]=c;str[i]='\0'; }
void pl(char *str) { rep(i,strlen(str)) put(str[i]); }
void gfi(ft &x) {
	register ft c = get(); x = 0; ft sn=1;
        for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;
        for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}
        x*=sn;
}
struct node {
	int x,y,i;
}q[311111];

typedef struct node nod;
int a[311111],cnt[1111111],answer=0,ans[311111],BLOCK=555;

bool cmp(node x, node y) {
	if(x.x/BLOCK != y.x/BLOCK) {
		return x.x/BLOCK < y.x/BLOCK;
	}
	return x.y < y.y;
}

/*int inline cmp(const void *xx,const void *yy) {
	nod *x = (nod *) xx;
	nod *y = (nod *) yy;
	if(x->x!=y->x) return (x->x>y->x)?1:-1;
	return (x->y>y->y)?1:(x->y<y->y)?-1:0;
}
*/
void add(int ind) {
	cnt[a[ind]]++;
	if(cnt[a[ind]]==1) answer++;
}

void rem(int ind) {
	cnt[a[ind]]--;
	if(cnt[a[ind]]==0) answer--;
}

int main() {
	int n,query;
	gfi(n);
	rep(i,n) gfi(a[i]);
	gfi(query);
	rep(i,query) {
		gfi(q[i].x);gfi(q[i].y);
		q[i].x--;q[i].y--;
		q[i].i=i;
	}
	sort(q,q+query,cmp);
	int ll=0,rr=0;
	rep(i,query) {
		int l=q[i].x,r=q[i].y;
		while(ll<l) rem(ll++);
		while(ll>l) add(--ll);
		while(rr<=r) add(rr++);
		while(rr>r+1) rem(--rr);
		ans[q[i].i]=answer;
	}
	rep(i,query) pi(ans[i]),pn;
	return 0;
}