wa#21求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[300005],v[300005],mps,bl[300005],m,zs[5005][5005],cnt[300005];
map<int,int> mp;
vector<int> in[300005];
int fqy(int l,int r,int x){
	return upper_bound(in[x].begin(),in[x].end(),r)-lower_bound(in[x].begin(),in[x].end(),l);
}
signed main(){
	v[0]=4e18;
	cin>>n;
	m=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		bl[i]=(i-1)/m+1;
		if(mp[a[i]]==0){
			mp[a[i]]=++mps;
			v[mps]=a[i];
		}
		a[i]=mp[a[i]];
		in[a[i]].push_back(i);
	}
	for(int i=1;i<=m;i++){
		memset(cnt,0,sizeof cnt);
		int ans=0,maxn=0;
		for(int j=(i-1)*m+1;j<=n;j++){
			cnt[a[j]]++;
			if(maxn<cnt[a[j]]||(maxn==cnt[a[j]]&&v[a[j]]<v[ans])){
				ans=a[j];
				maxn=cnt[a[j]];
			}
			zs[i][bl[j]]=ans;
		}
	}
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		int ans=zs[bl[l]+1][bl[r]-1];
		int fans=fqy(l,r,ans);
		for(int j=l;j<=min(bl[l]*m,r);j++){
			int fj=fqy(l,r,a[j]);
			if(fj>fans||(fj==fans&&v[a[j]]<v[ans])||ans==0){
				fans=fj;
				ans=a[j];
			}
		}
		if(bl[l]!=bl[r]){
			for(int j=(bl[r]-1)*m+1;j<=r;j++){
				int fj=fqy(l,r,a[j]);
				if(fj>fans||(fj==fans&&v[a[j]]<v[ans])||ans==0){
					fans=fj;
					ans=a[j];
				}
			}
		}
		cout<<v[ans]<<'\n';
	}
	return 0;
}