#include <bits/stdc++.h>
#define P pair
#define fi first 
#define se second 
using namespace std; const int N = 2e5 + 5, B = 354, inf = 0x3f3f3f3f;
int n, a[N], m, ans[N], le[N], ri[N], lsh, cnt, tmp; map<int, int> mp;
struct Query { int l, r, val, id; } q[N]; 
struct Node { int *p, v, t; }; stack<Node> s;
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
void ins(int x) {
    s.emplace(Node{&le[a[x]], le[a[x]], x}); 
    s.emplace(Node{&ri[a[x]], ri[a[x]], x});
    s.emplace(Node{&tmp, tmp, x}); le[a[x]] = min(le[a[x]], x); 
    ri[a[x]] = max(ri[a[x]], x); tmp = max(tmp, ri[a[x]] - le[a[x]]);
}
void del(int x) {
    for (; s.size() && s.top().t == x; s.pop()) *s.top().p = s.top().v;
}
signed main() {
    read(n); 
    for (int i = 1; i <= n; ++i) {
        read(a[i]); if (!mp[a[i]]) mp[a[i]] = ++lsh; a[i] = mp[a[i]];
    }
    read(m); memset(le, 0x3f, sizeof le);
    for (int i = 1, l, r; i <= m; ++i) {
        read(l); read(r); int lv = l / B, rv = r / B;
        if (lv == rv) {
            for (int j = l; j <= r; ++j) {
                le[a[j]] = min(le[a[j]], j); ri[a[j]] = max(ri[a[j]], j);
                ans[i] = max(ans[i], ri[a[j]] - le[a[j]]);
            }
            for (int j = l; j <= r; ++j) le[a[j]] = inf, ri[a[j]] = 0;
        } else q[++cnt] = {l, r, lv, i};
    }
    stable_sort(q + 1, q + cnt + 1, [&](Query u, Query v) {
        return u.val != v.val ? u.val < v.val : u.r < v.r;
    });
    for (int i = 1, l, r; i <= cnt; ++i) {
        int R = q[i].val * B + B - 1;
        if (i != 1 && q[i].val != q[i - 1].val)  while (l <= r) del(r--);
        l = R + 1, r = R; while (r < q[i].r) ins(++r); 
        while (l > q[i].l) ins(--l); ans[q[i].id] = tmp; while(l <= R) del(l++);
    }
    for (int i = 1; i <= m; ++i) print(ans[i]); return 0;
}