玄关，回滚莫队TLE 46pts

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005

int n,m,B;

inline int blk_id(int x) {
    return (x-1)/B+1;
}

inline int blkl(int id) {
    return (id-1)*B+1;
}

inline int blkr(int id) {
    return min(id*B,n);
}

int ans[N];
int col[N],v[N],len;

struct question
{
    int ql,qr,id;
    bool operator < (const question &_a) const 
    {
        if(blk_id(ql)==blk_id(_a.ql)) return qr<_a.qr;
        else return blk_id(ql)<blk_id(_a.ql);
    }
}que[N];

int lst_blk,pl,pr; 
int maxr[N],minl[N];
int new_maxr[N],new_minl[N];

void add(int p,int r[],int l[])
{
    r[col[p]]=max(r[col[p]],p);
    l[col[p]]=min(l[col[p]],p);
    return;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    
    for(int i=1;i<=n;++i)
    cin>>col[i],v[i]=col[i];
    
    cin>>m;
    B=ceil(1.0*n/sqrt(m));

    for(int i=1;i<=m;++i)
        cin>>que[i].ql>>que[i].qr,que[i].id=i;

    sort(v+1,v+n+1);
    sort(que+1,que+m+1);
    len=unique(v+1,v+n+1)-(v+1);
    
    for(int i=1;i<=n;++i) 
    {
        col[i]=lower_bound(v+1,v+len+1,col[i])-v;
        maxr[col[i]]=new_maxr[col[i]]=0;
        minl[col[i]]=new_minl[col[i]]=1e18;
    }

    pl=1,pr=lst_blk=0;
    for(int i=1;i<=m;++i)
    {
        int ql=que[i].ql,qr=que[i].qr;
        if(blk_id(ql)==blk_id(qr))
        {
            for(int j=ql;j<=qr;++j) 
			{
				add(j,new_maxr,new_minl);
	            ans[que[i].id]=max(ans[que[i].id],new_maxr[col[j]]-new_minl[col[j]]);
			}
            for(int j=ql;j<=qr;++j) new_maxr[col[j]]=0,new_minl[col[j]]=1e18;
        }else
        {
            if(blk_id(pl)!=lst_blk)
            {
                for(int j=pl;j<=pr;++j) minl[col[j]]=1e18,maxr[col[j]]=0;
                pl=blkr(blk_id(ql))+1,pr=blkr(blk_id(ql)),lst_blk=blk_id(ql);
            }

            while(pr<qr)
            {
                add(++pr,maxr,minl);
                ans[que[i].id]=max(ans[que[i].id],maxr[col[pr]]-minl[col[pr]]);
            }

            int templ=pl;
            while(templ>ql)
            {
                add(--templ,new_maxr,new_minl);
                ans[que[i].id]=max({ans[que[i].id],new_maxr[col[templ]]-new_minl[col[templ]],maxr[col[templ]]-new_minl[col[templ]]});
            }

            while(templ<pl) 
            {
                new_maxr[col[templ]]=0,new_minl[col[templ]]=1e18;
                templ++;
            } 
        }
    }

    for(int i=1;i<=m;++i) cout<<ans[i]<<"\n";

    return 0;
}