#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 998244353;

struct segt
{
    int dat[4194304];
    void clear()
    {
        memset(dat, 0, sizeof(dat));
    }
    void modify(int id, int val)
    {
        id |= 2097152;
        dat[id] = val;
        for(id >>= 1; id >= 1; id >>= 1) dat[id] = max(dat[id << 1], dat[id << 1 | 1]);
    }
    int query(int l, int r)
    {
        l |= 2097152; r |= 2097152;
        int ret = 0;
        while(l < r) {
            if(l & 1) ret = max(ret, dat[l]);
            if(!(r & 1)) ret = max(ret, dat[r]);
            l = (l + 1) >> 1; r = (r - 1) >> 1;
        }
        if(l == r) ret = max(ret, dat[l]);
        return ret;
    }
}t0, t1;

int n, m, a[2000005], ql[2000005], qr[2000005], ans[2000005];
int pocc[2000005];
vector<int> hvq[2000005];

int main()
{
    scanf("%d", &n);
    rep1(i, n) scanf("%d", &a[i]);
    scanf("%d", &m);
    rep(i, m) scanf("%d%d", &ql[i], &qr[i]);
    rep(i, m) hvq[qr[i]].push_back(i);
    
    rep1(i, n) {
        if(pocc[a[i]] != 0) {
            t0.modify(pocc[a[i]], 0);
            t1.modify(pocc[a[i]], i - pocc[a[i]] - 1);
        }
        pocc[a[i]] = i;
        t0.modify(i, n + 1 - i);
        rep(j, hvq[i].size()) {
            int cq = hvq[i][j];
            ans[cq] = max(ans[cq], t0.query(ql[cq], i) - n - 1 + i);
            ans[cq] = max(ans[cq], t1.query(ql[cq], i));
        }
    }
    
    t0.clear();
    rep1(i, n) hvq[i].clear();
    rep(i, m) hvq[ql[i]].push_back(i);
    rep1(i, n) pocc[a[i]] = 0;
    for(int i = n; i >= 1; i --) {
        if(pocc[a[i]] != 0) t0.modify(pocc[a[i]], 0);
        pocc[a[i]] = i;
        t0.modify(i, i);
        rep(j, hvq[i].size()) {
            int cq = hvq[i][j];
            ans[cq] = max(ans[cq], t0.query(i, qr[cq]) - i);
        }
    }
    
    rep(i, m) printf("%d\n", ans[i]);
    return 0;
}