#include<bits/stdc++.h>
#define db double
#define reg register
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ull unsigned long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=head[a];i;i=e[i].nxt)


using namespace std;
bool Handsome;
inline int rd(){
    reg int x=0;reg char o=getchar();reg bool O=0;
    for(;o<48 || 57<o;o=getchar())if(o=='-')O=1;
    for(;48<=o && o<=57;o=getchar())x=(x<<1)+(x<<3)+(o^48);
    return O?-x:x;
}
inline void Mi(int &x,int y){if(x>y && (x=y));}
inline void Mx(int &x,int y){if(x<y && (x=y));}
const int M=2e6+5;
int n,a[M],m,ans[M],pl[M];
struct node{int x,y,id;}tmp;
vector<node> g0[M],g1[M];
struct BIT0{
    int t[M];
    void add(int x,int y){
        for(;x;x-=x&-x)t[x]+=y;
    }
    int ask(int x){
        int res=0;
        for(;x<=n;x+=x&-x)res+=t[x];
        return res;
    }
}bit0;
struct BIT1{
    int t[M];
    void add(int x,int y){
        for(;x<=n;x+=x&-x)t[x]+=y;
    }
    int ask(int x){
        int res=0;
        for(;x;x-=x&-x)res+=t[x];
        return res;
    }
}bit1;
struct BIT2{
    int t[M];
    void add(int x,int y){
        for(;x;x-=x&-x)Mx(t[x],y);
    }
    int ask(int x){
        int res=0;
        for(;x<=n;x+=x&-x)Mx(res,t[x]);
        return res;
    }
}s;
bool Most;
int main(){
//    printf("%.2lfMB\n",(&Most-&Handsome)/1024.0/1024.0);
    rep(i,1,n=rd())a[i]=rd();
    rep(i,1,m=rd()){
        int x=rd(),y=rd();
        g0[y].pb((node){x,y,i});
        g1[x].pb((node){x,y,i});
    }
    rep(i,1,n){
        s.add(pl[a[i]]+1,i-pl[a[i]]-1);
        if(pl[a[i]])bit0.add(pl[a[i]],-1);
        bit0.add(pl[a[i]]=i,1);
        rep(j,0,g0[i].size()-1){
            int x=g0[i][j].x,id=g0[i][j].id;
            Mx(ans[id],s.ask(x));
            int z=bit0.ask(x)-1,l=1,r=i,res=i+1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(bit0.ask(mid)<=z)res=mid,r=mid-1;
                else l=mid+1;
            }
            Mx(ans[id],i-res+1);
        }
    }
    rep(i,1,n)pl[a[i]]=n+1;
    drep(i,n,1){
        if(pl[a[i]]<=n)bit1.add(pl[a[i]],-1);
        bit1.add(pl[a[i]]=i,1);
        rep(j,0,g1[i].size()-1){
            int y=g1[i][j].y,id=g1[i][j].id;
            int z=bit1.ask(y)-1,l=i,r=n,res=i-1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(bit1.ask(mid)<=z)res=mid,l=mid+1;
                else r=mid-1;
            }
            Mx(ans[id],res-i+1);
        }
    }
    rep(i,1,m)printf("%d\n",ans[i]);
    return 0;
}