#include <bits/stdc++.h>
using namespace std;

const int maxn = 2000010;
int n, m, a[maxn], nxt[maxn], lst[maxn], s[maxn << 2];
int ans[maxn], l[maxn], r[maxn], pre[maxn];
vector<int> Q[maxn];

#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
void modify(int k, int l, int r, int p, int v) {
    if (l == r) { s[k] = v; return; }
    if (mid >= p) modify(ls, l, mid, p, v);
    else modify(rs, mid + 1, r, p, v);
    s[k] = s[ls] + s[rs];
}

int find(int k, int l, int r, int ql, int qr) {
    if (!s[k] || max(l, ql) > min(r, qr)) return -1;
    if (l == r) return l;
    int t = find(ls, l, mid, ql, qr);
    if (~t) return t;
    return find(rs, mid + 1, r, ql, qr);
}

namespace SEG {
int mx[maxn << 2];
void init() { memset(mx, 0, sizeof(mx)); }

void modify(int k, int l, int r, int p, int v) {
    if (l == r) { mx[k] = max(mx[k], v); return; }
    if (mid >= p) modify(ls, l, mid, p, v);
    else modify(rs, mid + 1, r, p, v);
    mx[k] = max(mx[ls], mx[rs]);
}

int query(int k, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return mx[k];
    int s = 0;
    if (mid >= ql) s = query(ls, l, mid, ql, qr);
    if (mid < qr) s = max(s, query(rs, mid + 1, r, ql, qr));
    return s;
}
}  // namespace SEG

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &l[i], &r[i]);
    }
    auto solve = [&]() {
        fill(lst, lst + maxn, n + 1);
        vector<pair<int, int>> S;
        for (int i = n; i; i--) {
            nxt[i] = lst[a[i]], lst[a[i]] = i;
            S.emplace_back(nxt[i], i);
            Q[i].clear();
        }
        sort(S.begin(), S.end());
        for (int i = 1; i <= m; i++) {
            Q[r[i]].push_back(i);
        }
        memset(lst, 0, sizeof(lst));
        for (int i = 1; i <= n; i++) {
            pre[i] = lst[a[i]], lst[a[i]] = i;
        }
        SEG::init();
        memset(s, 0, sizeof(s));
        for (int i = 1, j = 0; i <= n; i++) {
            modify(1, 1, n, i, 1);
            if (pre[i]) SEG::modify(1, 1, n, pre[i], i - pre[i] - 1);
            for (; j < S.size() && S[j].first <= i; j++) {
                modify(1, 1, n, S[j].second, 0);
            }
            for (int j : Q[i]) {
                ans[j] = max(ans[j], i - find(1, 1, n, l[j], i));
                ans[j] = max(ans[j], SEG::query(1, 1, n, l[j], i));
            }
        }
    };
    solve();
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= m; i++) {
        l[i] = n - l[i] + 1, r[i] = n - r[i] + 1;
        swap(l[i], r[i]);
    }
    solve();
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}