/*******************************
| Author:  Albert_Wei
| Problem: F. Souvenirs
| Contest: Codeforces - Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
| URL:     https://codeforces.com/problemset/problem/765/F
| When:    2025-07-01 16:20:35
| 
| Memory:  512 MB
| Time:    3000 ms
*******************************/
#include <bits/stdc++.h>
// #define int long long
#define F(i, l, r) for (int i = l; i <= r; i ++)
#define G(i, r, l) for (int i = r; i >= l; i --)
using namespace std;

#define fi first
#define se second
#define MP make_pair
typedef long long LL;
typedef unsigned long long ull;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<ull, int> pui;

const int MOD = 998244353, N = 1e5 + 7, BL = 320;

template<typename T>
T& Fmin(T &x, T y) { return x = x < y ? x : y; }
template<typename T>
T& Fmax(T &x, T y) { return x = y < x ? x : y; }

LL read() {
    char c = getchar(); LL x = 0, p = 1;
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') p = -1, c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * p;
}

auto fplus = [](int x, int y) { return x + y < MOD ? x + y : x + y - MOD; };
auto fminus = [](int x, int y) { return x < y ? x - y + MOD : x - y; };
auto Fplus = [](int &x, int y) { x = fplus(x, y); };
auto Fminus = [](int &x, int y) { x = fminus(x, y); };
int fpow(int x, int y = MOD - 2) {
    int ans = 1;
    for (; y; x = (LL) x * x % MOD, y >>= 1)
        if (y & 1) ans = (LL) ans * x % MOD;
    return ans;
}

pii srt[BL][BL];
int n, m, B, C, L[N], R[N], len[BL], bel[N], a[N];
int res[N][BL], aa[BL][BL], pre[N], suf[N], b[N];

int main() {
    n = read(), B = 316, C = (n + B - 1) / B;
    F(i, 1, n) a[i] = b[i] = read();
    sort(b + 1, b + n + 1);
    int V = unique(b + 1, b + n + 1) - b - 1;
    F(i, 1, n) a[i] = lower_bound(b + 1, b + V + 1, a[i]) - b;
    memset(aa, 0x3f, sizeof aa), memset(res, 0x3f, sizeof res);
    F(i, 1, C) {
        memset(pre, 0, sizeof pre), memset(suf, 0, sizeof suf);
        L[i] = R[i - 1] + 1, R[i] = min(i * B, n), len[i] = R[i] - L[i] + 1;
        F(j, L[i], R[i]) srt[bel[j] = i][j - L[i] + 1] = MP(a[j], j), pre[a[j]] = suf[a[j]] = a[j];
        sort(srt[i] + 1, srt[i] + len[i] + 1);
        F(j, 2, len[i]) Fmin(aa[i][i], b[srt[i][j].fi] - b[srt[i][j - 1].fi]);
        F(j, 1, V) if (!pre[j]) pre[j] = pre[j - 1];
        G(j, V, 1) if (!suf[j]) suf[j] = suf[j + 1];
        F(j, 1, n) if (bel[j] != i) {
            if (pre[a[j]]) Fmin(res[j][i], b[a[j]] - b[pre[a[j]]]);
            if (suf[a[j]]) Fmin(res[j][i], b[suf[a[j]]] - b[a[j]]);
        }
    }
    F(i, 1, n) {
        G(j, bel[i] - 1, 1) Fmin(res[i][j], res[i][j + 1]);
        F(j, bel[i] + 1, C) Fmin(res[i][j], res[i][j - 1]);
    }
    F(i, 1, C) F(j, i + 1, C) {
        aa[i][j] = min(aa[i][j - 1], aa[j][j]);
        F(k, L[j], R[j]) Fmin(aa[i][j], res[k][i]);
    }
    m = read();
    for (int i = 1, l, r; i <= m; i ++) {
        l = read(), r = read();
        int ans = aa[bel[l] + 1][bel[r] - 1], lst = 0;
        auto slv = [&](int x, int y) {
            int val = srt[x][y].fi, id = srt[x][y].se;
            if (l <= id && id <= r) {
                if (lst) Fmin(ans, b[val] - b[lst]);
                lst = val;
            }
        };
        if (bel[l] != bel[r]) {
            F(j, l, R[bel[l]]) Fmin(ans, res[j][bel[r] - 1]);
            F(j, L[bel[r]], r) Fmin(ans, res[j][bel[l] + 1]);
            for (int j = 1, k = 1; j <= len[bel[l]] + 1; j ++) {
                while (k <= len[bel[r]] && (j == len[bel[l]] + 1 || srt[bel[r]][k] <= srt[bel[l]][j])) slv(bel[r], k ++);
                if (j <= len[bel[l]]) slv(bel[l], j);
            }
        } else F(j, 1, len[bel[l]]) slv(bel[l], j);
        cout << ans << '\n';
    }
    return 0;
}