88pts, TLE on #8 (2.00s), #9 (2.20s), #10 (2.20s).

#include<bits/stdc++.h>
// #pragma G++ optimize(2)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
int read() {
	int x=0,f=1;
	char ch=getchar_unlocked();
	while(ch<'0'||ch>'9') {
		if(ch=='-') f=-1;
		ch=getchar_unlocked();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar_unlocked();
	}
	return x*f;
}
void write(int x) {
	if(x<0) {
		putchar_unlocked('-');
		x=-x;
	}
	static int sta[35];
	int top=0;
	do {
		sta[top++]=x%10;
		x/=10;
	} while(x);
	while(top) putchar_unlocked(sta[--top]+'0');
}
const int N=1e6+5;
int n,block,a[N];
int iidx=0,iiidx[N];
struct Query {
	int id,l,r;
	bool operator< (const Query &B) const {
		int posA=(l-1)/block+1,posB=(B.l-1)/block+1;
		if(posA!=posB) return posA<posB;
		if(posA&1) return r<B.r;
		else return r>B.r;
	}
} que[N];
int cnt[N],pos[N],ans[N];
bool cmp(Query A,Query B) {
	int posA=(A.l-1)/block+1,posB=(B.l-1)/block+1;
	if(posA!=posB) return posA<posB;
	if(posA&1) return A.r<B.r;
	else return A.r>B.r;
}
int curans=0;
// void add(int x) {
// 	cnt[a[x]]++;
// 	if(cnt[a[x]]==1) curans++;
// }
// void del(int x) {
// 	cnt[a[x]]--;
// 	if(cnt[a[x]]==0) curans--;
// }
int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	n=read();
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		// pos[i]=(i-1)/block+1;
		if(!iiidx[a[i]]){
			iiidx[a[i]]=++iidx;
		}
		a[i]=iiidx[a[i]];
	}
	int m;cin>>m;
	for(int i=1;i<=m;i++) {
		que[i].id=i;
		que[i].l=read(),que[i].r=read();
	}
	block=1.0*n/sqrt(m);
	sort(que+1,que+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
		while(l<que[i].l) {
			// del(l++);
			cnt[a[l]]--;
			if(cnt[a[l]]==0) curans--;
			l++;
		}
		while(l>que[i].l) {
			// add(--l);
			l--;
			cnt[a[l]]++;
			if(cnt[a[l]]==1) curans++;
		}
		while(r<que[i].r) {
			// add(++r);
			r++;
			cnt[a[r]]++;
			if(cnt[a[r]]==1) curans++;
		}
		while(r>que[i].r) {
			// del(r--);
			cnt[a[r]]--;
			if(cnt[a[r]]==0) curans--;
			r--;
		}
		ans[que[i].id]=curans;
	}
	for(int i=1;i<=m;i++) {
		write(ans[i]);
		putchar_unlocked('\n');
	}
	return 0;
}