16 $pts$

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200005],lslen;
int ls[200005];
int tot[200005];
struct node
{
	int l,r,id;
	bool operator <(const node &n)const
	{
		return tot[l]<tot[n.l]||(tot[l]==tot[n.l]&&r<n.r);
	}
}arr[200005];
int len;	
int ans[200005],vis[200005][2],_r[200005];
int cnt[200005][2];
int sum=0;
inline void add(int x,int &qwq)
{
	vis[a[x]][0]=min(vis[a[x]][0],x);
	vis[a[x]][1]=max(vis[a[x]][1],x);
	qwq=max(vis[a[x]][1]-vis[a[x]][0],qwq);
}
inline void del(int x,int bj)
{
	if(bj==0)
	{
		if(vis[a[x]][1]==x)
		vis[a[x]][1]=0;
	}
	else if(bj==1)
	{
		if(vis[a[x]][0]==x)
		vis[a[x]][0]=INT_MAX;
	}
}
int main()
{
//	freopen("P5906_1.in","r",stdin);
//	feeop
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		ls[i]=a[i];
	}
	scanf("%d",&m);
	stable_sort(ls+1,ls+n+1);
	lslen=unique(ls+1,ls+n+1)-ls-1;
	len=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=lower_bound(ls+1,ls+lslen+1,a[i])-ls;
		cnt[a[i]][0]=vis[a[i]][0]=INT_MAX;
	}
	for(int i=1;i<=len;++i)
	{
		_r[i]=i*len;
		for(int j=1;j<=len;++j)
		{
			tot[j+(i-1)*len]=i;
		}
	}
	for(int i=len*len+1;i<=n;++i)
	{
		tot[i]=len+1;
		_r[len+1]=n;
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&arr[i].l,&arr[i].r);
		arr[i].id=i;
	}
	int l=1,r=0;
	int last_block=0;
	stable_sort(arr+1,arr+m+1);
	for(int i=1;i<=m;++i)
	{
		if(tot[arr[i].l]==tot[arr[i].r])
		{
			int nowans=0;
			for(int j=arr[i].l;j<=arr[i].r;++j)
			{
				cnt[a[j]][0]=min(cnt[a[j]][0],j);
				cnt[a[j]][1]=max(cnt[a[j]][1],j);
				nowans=max(nowans,cnt[a[j]][1]-cnt[a[j]][0]);
			}
			ans[arr[i].id]=nowans;
			for(int j=arr[i].l;j<=arr[i].r;++j)
			{
				cnt[a[j]][0]=INT_MAX;
				cnt[a[j]][1]=0;
			}
		}
		else
		{
			if(tot[arr[i].l]!=last_block)
			{
				while(r>_r[tot[arr[i].l]])
				del(r--,0);
     		    while(l<_r[tot[arr[i].l]]+1)
				del(l++,1);
				last_block=tot[arr[i].l];
				sum=0;
			}
			int _l=l;
			while(r<arr[i].r)
			add(++r,sum);
			int sum2=sum;
			while(_l>arr[i].l)
			add(--_l,sum2);
			ans[arr[i].id]=sum2;
			while(_l<l)
			del(_l++,1);
		}
	}
	for(int i=1;i<=m;++i)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}