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

const int MAXN = 2000005;

int n, m;
int a[MAXN], ans[MAXN];
int lv[MAXN], rv[MAXN];
int head[MAXN], nxt[MAXN];

int last[MAXN], val[MAXN << 2], lzy[MAXN << 2];

void build(int i, int l, int r) {
    val[i] = INT_MIN / 2, lzy[i] = 0;

    if (l == r) {
        return;
    }

    int mid = (l + r) / 2;

    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
}

void push(int i, int l, int mid, int r) {
    if (lzy[i]) {
        val[i * 2] = lzy[i] - l;
        val[i * 2 + 1] = lzy[i] - mid - 1;
        lzy[i * 2] = lzy[i * 2 + 1] = lzy[i];
        lzy[i] = 0;
    }
}

void upd(int low, int high, int v, int i, int l, int r) {
    if (high < l || r < low) {
        return;
    }
    if (low <= l && r <= high) {
        val[i] = v - l, lzy[i] = v;
        return;
    }

    int mid = (l + r) / 2;
    
    push(i, l, mid, r);
    upd(low, high, v, i * 2, l, mid);
    upd(low, high, v, i * 2 + 1, mid + 1, r);
    
    val[i] = max(val[i * 2], val[i * 2 + 1]);
}

int query(int low, int high, int i, int l, int r) {
    if (high < l || r < low) {
        return 0;
    }
    if (low <= l && r <= high) {
        return val[i];
    }
    
    int mid = (l + r) / 2;

    push(i, l, mid, r);

    return max(query(low, high, i * 2, l, mid), query(low, high, i * 2 + 1, mid + 1, r));
}

void solve() {
    memset(last, 0, sizeof last);
    memset(head, 0, sizeof head);

    for (int i = 1; i <= m; i++) {
        nxt[i] = head[rv[i]], head[rv[i]] = i;
    }

    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        if (i > 0) {
            upd(last[a[i]] + 1, i - 1, i, 1, 1, n);
        }
        last[a[i]] = i;

        for (int j = head[i]; j != 0; j = nxt[j]) {
            ans[j] = max(ans[j], query(lv[j], i, 1, 1, n));
        }
    }
}

int main(int argc, char **argv) {
    cin.sync_with_stdio(false), cin.tie(nullptr);

    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cin >> m;

    for (int i = 1; i <= m; i++) {
        cin >> lv[i] >> rv[i];
        ans[i] = 0;
    }

    solve();

    reverse(a + 1, a + 1 + n);

    for (int i = 1; i <= m; i++) {
        swap(lv[i], rv[i]);
        lv[i] = n - lv[i] + 1;
        rv[i] = n - rv[i] + 1;
    }

    solve();

    for (int i = 1; i <= m; i++) {
        cout << ans[i] << "\n";
    }
}