#include <bits/stdc++.h>
#define RAN(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define I (J + 1)
#define J (i + j >> 1)
#define P (k << 1)
#define S (P ^ 1)
using namespace std;
typedef long long ll;

template <class T1, class T2>
inline void upd1(T1& a, const T2& b) {
    a = a < b ? a : b;
}

template <class T1, class T2>
inline void upd2(T1& a, const T2& b) {
    a = b < a ? a : b;
}

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

struct Ano {
    operator int() {
        int x = 0, y = 0, c = getchar();
        while (c < 48) {
            y = c == 45;
            c = getchar();
        }
        while (c > 47) {
            x = x*10 + c-48;
            c = getchar();
        }
        return y ? -x : x;
    }
} buf;

constexpr int N = 2e6 + 5;

struct query {
    int u, v, w;
} t[N];

int n, w[N], p[N], q[N], l[N], c[N];
vector<query*> a[N], b[N];

inline void ins(int i, int v) {
    for (; i <= n; i += i & -i) {
        upd2(c[i], v);
    }
}

inline void ins(int i) {
    ins(i, i);
}

inline int ask(int i) {
    int s = 0;
    for (; i; i ^= i & -i)
        upd2(s, c[i]);
    return s;
}

int main() {
    n = buf;
    for (int i = 1; i <= n; ++i) {
        w[i] = buf;
        if (l[w[i]]) {
            p[i] = l[w[i]];
            q[p[i]] = i;
        } else {
            ins(i);
        }
        l[w[i]] = i;
    }
    int m = buf;
    for (int i = 0; i < m; ++i) {
        t[i].u = buf;
        t[i].v = buf;
        a[t[i].u].pb(t + i);
        b[t[i].v].pb(t + i);
    }
    for (int i = 1; i <= n; ++i) {
        for (auto j: a[i]) {
            upd2(j->w, ask(j->v) - j->u);
        }
        if (q[i]) {
            ins(q[i]);
        }
    }
    fill_n(c + 1, n, 0);
    for (int i = 1; i <= n; ++i) {
        if (!q[i]) {
            ins(n - i + 1);
        }
    }
    for (int i = n; i >= 1; --i) {
        for (auto j: b[i]) {
            upd2(j->w, j->v - (n - ask(n - j->u + 1) + 1));
        }
        if (p[i]) {
            ins(n - p[i] + 1);
        }
    }
    fill_n(c + 1, n, 0);
    for (int i = 1; i <= n; ++i) {
        if (p[i]) {
            ins(n - p[i] + 1, i - p[i] - 1);
        }
        for (auto j: b[i]) {
            upd2(j->w, ask(n - j->u + 1));
        }
    }
    for (int i = 0; i < m; ++i) {
        printf("%d\n", t[i].w);
    }
}