56分，TLE了11个点

#include<bits/stdc++.h>
using namespace std;
const int maxN=1e6+9;
struct Node{
	int l,r,id;
}a[maxN];
int n,m,c[maxN],lst[maxN],val[maxN],ans[maxN];
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (isdigit(ch)){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
void write(int x){
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
inline int lowbit(int x){return x&-x;}
void update(int x,int v){
	for (;x<=n;x+=lowbit(x)) c[x]+=v;
}
int query(int x){
	int ans=0;
	for (;x;x-=lowbit(x)) ans+=c[x];
	return ans;
}
inline bool cmp(Node a,Node b){
	return a.r<b.r;
}
int main(){
	n=read();
	for (register int i=1;i<=n;i++) val[i]=read(),lst[i]=n+1;
	m=read();
	for (register int i=1;i<=m;i++) a[i].l=read(),a[i].r=read(),a[i].id=i;
	sort(a+1,a+m+1,cmp);
	for (register int i=1,j=1;i<=m;i++){
		for (;j<=a[i].r;j++) update(lst[val[j]],-1),update(j,1),lst[val[j]]=j;
		ans[a[i].id]=query(a[i].r)-query(a[i].l-1);
	}
	for (register int i=1;i<=m;i++) write(ans[i]),puts("");
	return 0;
}

谢谢