#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn = 2000010;
int a[Maxn], b[Maxn], val[Maxn];
int n, m;
struct Query{
    int l, r, id;
}Q[Maxn];
int len, sum;
int Ans[Maxn];
int belong[Maxn], sl[Maxn], sr[Maxn];
bool cmp(Query x, Query y){
    return (belong[x.l] ^ belong[y.l]) ? belong[x.l] < belong[y.l] : x.r < y.r;
}
int cnt[Maxn], vis[Maxn], Last[Maxn], la[Maxn], fir[Maxn], Clean[Maxn], top;
signed main(){
    // ios::sync_with_stdio(false);
    // freopen("P5906.in", "r", stdin);
    // freopen("P5906.out", "w", stdout)
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i], val[i] = a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    int tot = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1 ; i <= n ; i++) val[i] = lower_bound(b + 1, b + tot + 1 ,val[i]) - b;
    len = sqrt(n);
    sum = ceil((double) n / len);
    for(int i = 1 ; i <= sum ; i++){
        sl[i] = (i - 1) * len + 1;
        sr[i] = i * len;
        for(int j = sl[i] ; j <= sr[i] ; j++)
            belong[j] = i;
    }
    sr[sum] = n;
    cin >> m;
    for(int i = 1 ; i <= m ; i++){
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }
    sort(Q + 1, Q + m + 1, cmp);
    int i = 1;
    for(int x = 1 ; x <= sum ; x++){
        int l = sr[x] + 1, r = sr[x];
        int ans = 0, top = 0;
        for(; belong[Q[i].l] == x ; i++){
            if(belong[Q[i].l] == belong[Q[i].r]){
                int L = Q[i].l, R = Q[i].r;
                int s = 0;
                for(int j = L ; j <= R ; j++) vis[val[j]] = 0;
                for(int j = L ; j <= R ; j++){
                    if(!Last[val[j]]) Last[val[j]] = j;
                    else s = max(s, j - Last[val[j]]);
                }
                Ans[Q[i].id] = s;
                continue;
            }
            int L = Q[i].l, R = Q[i].r;
            while(r < R){
                r++;
                la[val[r]] = r;
                if(!fir[val[r]]){
                    fir[val[r]] = r;
                    Clean[++top] = val[r];
                }
                ans = max(ans, r - fir[val[r]]);
            }
            int now = ans;
            while(l > L){
                l--;
                if(la[val[l]]) ans = max(ans, la[val[l]] - l);
                else la[val[l]] = l;
            }
            Ans[Q[i].id] = ans;
            while(l <= sr[x] + 1){
                if(la[val[l]] == l) la[val[l]] = 0;
                l++;
            }
            ans = now;
        }
        for(int i = 1 ; i <= top ; i++) la[Clean[i]] = fir[Clean[i]] = 0;
    }
    for(int i = 1 ; i <= m ; i++){
        cout << Ans[i] << '\n';
        if(Ans[i] == 197) cout << i << endl;
    } 
    return 0;
}