// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;

template <typename T> void chkMax(T &x, T y) { if (y > x) x = y; }
template <typename T> void chkMin(T &x, T y) { if (y < x) x = y; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2e6 + 5;

int n, a[N], m, ans[N], t, cnt[N];
 
struct E{
    int l, r;
} e[N];

struct Q{
    int l, r, id;
} q[N];

int c[N];

void inline add(int x, int k) {
    for (; x <= n; x += x & -x) chkMax(c[x], k);
}

int inline ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) chkMax(res, c[x]);
    return res;
}

bool inline cmpE1(E x, E y) {
    return x.l < y.l;
}

bool inline cmpQ1(Q x, Q y) {
    return x.l < y.l;
}

void inline work1() {
    sort(e + 1, e + 1 + t, cmpE1);
    sort(q + 1, q + 1 + m, cmpQ1);
    for (int i = m, j = t; i; i--) {
        while (j && e[j].l >= q[i].l) {
            add(e[j].r, e[j].r - e[j].l - 1);
            j--;
        }
        chkMax(ans[q[i].id], ask(q[i].r));
    }
}

int mx[N << 2];

set<int> s;

typedef set<int>::iterator SIT;

void inline work2() {
    for (int i = 1, j = 1; i <= m; i++) {
        while (j <= t && e[j].l < q[i].l) {
            s.insert(e[j].r);
            j++;
        }
        SIT it = s.upper_bound(q[i].r);
        if (it != s.begin()) {
            --it;
            int r = *it;
            if (q[i].l <= r) chkMax(ans[q[i].id], r - q[i].l);
        }
    }
}

bool inline cmpE2(E x, E y) {
    return x.r < y.r;
}

bool inline cmpQ2(Q x, Q y) {
    return x.r < y.r;
}

void inline work3() {
    sort(e + 1, e + 1 + t, cmpE2);
    sort(q + 1, q + 1 + m, cmpQ2);
    s.clear();
    for (int i = m, j = t; i; i--) {
        while (j && e[j].r > q[i].r) {
            s.insert(e[j].l);
            j--;
        }
        SIT it = s.lower_bound(q[i].l);
        if (it != s.end()) {
            int l = *it;
            if (l <= q[i].r) chkMax(ans[q[i].id], q[i].r - l);
        }
    }
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        e[++t] = (E) { cnt[a[i]], i };
        cnt[a[i]] = i;
    }
    for (int i = 1; i <= 2000000; i++) 
        if (cnt[i]) e[++t] = (E) { cnt[i], n + 1 };
    read(m);
    for (int i = 1; i <= m; i++) {
        read(q[i].l), read(q[i].r), q[i].id = i;
    }
    work1();
    work2();
    work3();
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}