自己按照历史研究打的板子，不知道假没假，该卡常的地方都卡了，求助了qwq

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=2e5+10;
int N,M,Val[MAXN],Uni;
int Cnt[MAXN],ans[MAXN];
struct query
{
    int l,r,id;
    bool operator<(const query &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        return r<x.r;
    }
}Q[MAXN];
std::vector<int>Nums;
inline void add(int pos,int dir,int &res)
{
    if(!Cnt[pos]) Cnt[pos]=dir;
    res=std::max(res,dir-Cnt[pos]);
}
std::vector<int>Change;
inline void Solve()
{
    std::sort(Q+1,Q+1+M);
    for(int i=1;i<=M;)
    {
        int j=i;
        while(j<=M&&Q[j].l/Uni==Q[i].l/Uni) ++j;
        int right=(Q[i].l/Uni)*Uni+Uni-1;
        while(i<j)
        {
            int res=0;
            auto q=Q[i];
            for(int k=q.l;k<=q.r;++k) add(Val[k],k,res);
            ans[q.id]=res;
            for(int k=q.l;k<=q.r;++k) Cnt[Val[k]]=0;
            ++i;
        }
        int res=0;
        int l=right,r=right+1;
        while(i<j)
        {
            auto q=Q[i];
            while(l<q.r) ++l,add(Val[l],l,res),Change.push_back(Val[l]);
            int backup=res;
            while(r>q.l) --r,add(Val[r],r,res),Change.push_back(Val[r]);
            ans[q.id]=res;
            while(r<right+1) Cnt[Val[r++]]=0;
            res=backup;
            ++i;
        }
        for(auto cl:Change) Cnt[Change[cl]]=0;
        Change.clear();
    }
}
int main()
{
    // freopen("backup-moalgo.in","r",stdin);
    // freopen("backup-moalgo.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Val[i]),Nums.push_back(Val[i]);
    std::sort(Nums.begin(),Nums.end());
    Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
    for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums.begin(),Nums.end(),Val[i])-Nums.begin();
    read(M);
    Uni=std::sqrt((double)N*N/(double)M)+1;
    for(int i=1;i<=M;++i)
    {
        read(Q[i].l,Q[i].r);
        Q[i].id=i;
    }
    Solve();
    for(int i=1;i<=M;++i) write(ans[i]),puts("");
    return 0;
}
/*
8
1 6 2 2 3 3 1 6
5
1 4
2 5
2 8
5 6
1 7
*/