记录编号	308722	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	2.119 s
提交时间	2016-09-18 16:02:31	内存使用	4.40 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 50020
#define maxm 200020
using namespace std;
struct Num{
	int v,pos;
}a[maxn];
struct Que{
	int l,r,pos;
}q[maxm];
int b[maxn],n,m,Color[maxn],num[maxm],ans[maxm];
bool comp(const Num &a,const Num &b){
	return a.v<b.v;
}
bool comp1(const Que &a,const Que &b){
	if(Color[ a.l ]!=Color[ b.l ])
	return Color[ a.l ]<Color[ b.l ];
	return a.r<b.r;
}
void _work(){
	int l=1,r=1,cnt=1;num[b[1]]=1;
	for(int i=1;i<=m;i++){
		while(r<q[i].r){
			r++;
			if(++num[b[r]]==1)cnt++;
		}
		while(r>q[i].r){
			if(--num[b[r]]==0)cnt--;
			r--;
		}
		while(l<q[i].l){
			if(--num[b[l]]==0)cnt--;
			l++;
		}
		while(l>q[i].l){
			l--;
			if(++num[b[l]]==1)cnt++;
		}
		ans[q[i].pos]=cnt;
	}
}
/*void _work(){
	int l = 1, r = 1, cnt = 1;  num[b[1]]++;
	
	for(int i=1;i<=m;i++){//这地儿 看着来吧，自己模拟 
		while(r<q[i].r){ r++; if(++num[b[r]]==1) cnt++; }
		
		while(r>q[i].r){ if(--num[b[r]]==0) cnt--; r--; }
		
		while(l>q[i].l){ l--; if(++num[b[l]]==1) cnt++; }
		
		while(l<q[i].l){ if(--num[b[l]]==0) cnt--; l++; }
		
		ans[q[i].pos] = cnt;
	}
}*/
int main(){
	freopen("diff.in","r",stdin);freopen("diff.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].v);a[i].pos=i;
		Color[i]=i/sqrt(n+0.0);
	}
	sort(a+1,a+n+1,comp);
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i].v!=a[i-1].v)cnt++;
		b[a[i].pos]=cnt;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);q[i].pos=i;
	}
	sort(q+1,q+m+1,comp1);
	_work();
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	fclose(stdin);fclose(stdout);
	//while(1);
	return 0;
}