//AC


#include <bits/stdc++.h>


const int MAX = 1e6 + 5;


int N{}, A[MAX]{}, Q{};
int BlockLen{}, L = 1, R{},  BlockNum{};
int Sum{}, Ans[MAX]{}, Cnt[MAX]{};


int Belong[MAX]{};
int Flag[MAX]{}, Pre[MAX]{}, Suf[MAX]{};


struct COpt {
	int L{}, R{}, Id{};
}Opt[MAX];


int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> N;
	for (int i = 1; i <= N; ++i) std::cin >> A[i];
	BlockLen = sqrt(N);
	if (N % BlockLen) BlockNum++;
	for (int i = 1; i <= N; ++i) Belong[i] = (i - 1) / BlockLen + 1;
	std::cin >> Q;
	for (int i = 1; i <= Q; ++i) std::cin >> Opt[i].L >> Opt[i].R, Opt[i].Id = i;

	std::sort(Opt + 1, Opt + 1 + Q, [](COpt A, COpt B) {
		if (Belong[A.L] == Belong[B.L]) return A.R < B.R;
		return A.L < B.L;
	});

	for (int i = 1; i <= N; ++i) Pre[i] = Flag[A[i]], Flag[A[i]] = i;

	memset(Flag, 0x3f, sizeof(Flag));
	for (int i = N; i >= 1; --i) Suf[i] = Flag[A[i]], Flag[A[i]] = i;

	for (int i = 1; i <= Q; ++i) {
		while (L > Opt[i].L) Sum += (Suf[--L] > R);
		while (L < Opt[i].L) Sum -= (Suf[L++] > R);
		while (R > Opt[i].R) Sum -= (Pre[R--] < L);
		while (R < Opt[i].R) Sum += (Pre[++R] < L);
		Ans[Opt[i].Id] = Sum;
	}

	for (int i = 1; i <= Q; ++i) std::cout << Ans[i] << '\n';
}

//TLE 28pts
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt[1000005],ans;
int a[1000005],q[1000005],Ans[1000005];
struct node{
	int l,r,id,ans;
}b[1000005];
bool cmp(node x,node y){
	if(q[x.l]==q[y.l]) return x.r<y.r;
	return  x.l<y.l; 
}
bool cmp2(node x,node y){
	return x.id<y.id;
}
void add(int p,int x){
	cnt[p]+=x;
	if(cnt[p]==1&&x==1) ans++;
	if(cnt[p]==0&&x==-1) ans--;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	int k=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i],q[i]=(i-1)/k+1;
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>b[i].l>>b[i].r;
		b[i].id=i;
	}
	stable_sort(b+1,b+1+m,cmp);
	for(int l=1,r=0,i=1;i<=m;i++){
		while(l>b[i].l) add(a[--l],1);
		while(r<b[i].r) add(a[++r],1);
		while(l<b[i].l) add(a[l++],-1);
		while(r>b[i].r) add(a[r--],-1);
		Ans[b[i].id]=ans;
	}
//	stable_sort(b+1,b+1+m,cmp2);
	for(int i=1;i<=m;i++){
		cout<<Ans[i]<<'\n';
	}
	return 0;
}