#include<bits/stdc++.h>
using std::cin;
using std::cout;
typedef long long ll;
const int N = 2000005;
int n, m;
int a[N];
struct pr { int l, r; } b[N];
struct qy { int l, r, id; } q[N];
int la[N], cc;
int ans[N], pre[N], nxt[N];
inline bool cmp0(const qy & x, const qy & y) { return x.r < y.r; }
inline bool cmp1(const pr & x, const pr & y) { return x.r < y.r; }
inline bool cmp2(const qy & x, const qy & y) { return x.l < y.l; }
int bit[N];
inline void up(int & x, int y) { if(x < y) x = y; }
inline void upt(int pos, int v) {
    for(;pos;pos &= pos - 1) up(bit[pos], v);
}
inline int test(int pos) {
    int ans = 0;
    for(;pos <= n;pos += pos & -pos) up(ans, bit[pos]);
    return ans;
}

inline void solve() {
    static int bit[N];
    memset(la, 0, sizeof(la));
    memset(bit, 0, sizeof(bit));
    for(int i = 1;i <= n;++i) pre[i] = la[a[i]], la[a[i]] = i;
    std::sort(q + 1, q + m + 1, cmp0);

    for(int i = 1, j = 1;i <= m;++i) {
        int l = q[i].l, r = q[i].r, ans = 0;
        for(;j <= r;++j) {
            for(int x = pre[j] + 1;x <= n + 1;x += x & -x) {
                up(bit[x], j);
            }
        }
        for(int k = l;k;k &= k - 1)
            up(ans, bit[k]);
        up(::ans[q[i].id], ans - l);
    }
}
int main() {
    std::ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i) {
        cin >> a[i];
        if(la[a[i]] < i - 1) b[++cc] = {la[a[i]], i};
        la[a[i]] = i;
    }
    cin >> m;
    for(int i = 1;i <= m;++i) cin >> q[i].l >> q[i].r, q[i].id = i;
    std::sort(q + 1, q + m + 1, cmp0);
    std::sort(b + 1, b + cc + 1, cmp1);
    for(int i = 1, p0 = 1, p1 = 1;i <= n;++i) {
        for(;p0 <= cc && b[p0].r == i;++p0) upt(b[p0].l, b[p0].r - b[p0].l - 1);
        for(;p1 <= m && q[p1].r == i;++p1) up(ans[q[p1].id], test(q[p1].l));
    }
    solve();
    std::reverse(a + 1, a + n + 1);
    for(int i = 1;i <= m;++i) {
        std::swap(q[i].l, q[i].r);
        q[i].l = n + 1 - q[i].l;
        q[i].r = n + 1 - q[i].r;
    }
    solve();
    for(int i = 1;i <= m;++i) {
        cout << ans[i] << '\n';
    }
}