#include <bits/stdc++.h>
using namespace std;
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;
template <typename T>
inline void read(T &x) {
  char ch, t = 0;
  x = 0;
  while (!isdigit(ch = (iS == iT
                            ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)))
    t |= ch == '-';
  while (isdigit(ch))
    x = x * 10 + (ch ^ 48),
    ch = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
  x = t ? -x : x;
}
inline int read_int() {
  int x;
  return read(x), x;
}
inline long long read_ll() {
  long long x;
  return read(x), x;
}
template <typename T>
inline void chkmin(T &a, T b) {
  a = a < b ? a : b;
}
template <typename T>
inline void chkmax(T &a, T b) {
  a = a > b ? a : b;
}
const int SZ = 320;
const int MAXN = 100010;
const int inf = 2147483647;
struct Node {
  int v, p;
  Node() {}
  Node(int v, int p) : v(v), p(p) {}
  friend bool operator<(Node a, Node b) { return a.v < b.v; }
} A[325][325];
int F[325][325][325];
int Ans[325];
int a[MAXN];
int L[325];
int main() {
  int n = read_int(), sz = 0, N = 1;
  for (int i = 1; i <= n; i++) {
    A[N][++sz] = Node(a[i] = read_int(), i);
    if (sz == SZ) L[N++] = sz, sz = 0;
  }
  L[N] = sz, N -= !sz;
  for (int i = 1; i <= N; i++) {
    sort(A[i] + 1, A[i] + 1 + L[i]);
    A[i][L[i] + 1].v = inf, A[i][0].v = inf;
    int &res = Ans[i] = inf;
    for (int j = 2; j <= L[i]; j++) chkmin(res, A[i][j].v - A[i][j - 1].v);
  }
  memset(F, 63, sizeof(F));
  for (int i = 1; i <= N; i++)
    for (int j = i + 1; j <= N; j++) {
      int ci = (i - 1) * SZ, cj = (j - 1) * SZ;
      for (int a = 1, b = 1; a <= L[i] || b <= L[j];) {
        if (A[i][a] < A[j][b])
          F[i][A[i][a].p - ci][j] =
              min(abs(A[i][a].v - A[j][b].v), abs(A[i][a].v - A[j][b - 1].v)),
                           ++a;
        else
          F[j][A[j][b].p - cj][i] =
              min(abs(A[j][b].v - A[i][a].v), abs(A[j][b].v - A[i][a - 1].v)),
                           ++b;
      }
    }
  for (int i = 1; i <= N; i++) {
    for (int p = 1; p <= L[i]; p++)
      for (int j = i - 1; j >= 1; j--)
        chkmin(F[i][p][j], min(F[i][p - 1][j], F[i][p][j + 1]));
    for (int p = L[i]; p >= 1; p--)
      for (int j = i + 1; j <= N; j++)
        chkmin(F[i][p][j], min(F[i][p + 1][j], F[i][p][j - 1]));
  }
  int q = read_int();
  while (q--) {
    int l = read_int(), r = read_int(), pL = (l - 1) / SZ + 1,
        pR = (r - 1) / SZ + 1;
    int res = inf;
    for (int i = pL + 1; i <= pR - 1; i++)
      chkmin(res, min(F[i][1][pR - 1], Ans[i]));
    if (pL == pR) {
      int len = L[pL], las = -1;
      for (int i = 1; i <= len; i++) {
        if (l <= A[pL][i].p && A[pL][i].p <= r) {
          int v = A[pL][i].v;
          if (~las) chkmin(res, v - las);
          las = v;
        }
      }
    } else {
      int pl = l - (pL - 1) * SZ;
      int pr = r - (pR - 1) * SZ;
      chkmin(res, min(F[pL][pl][pR - 1], F[pR][pr][pL + 1]));
      int la = L[pL], lb = L[pR], av = -1, bv = -1, lav = -1, lbv = -1,
          lap = -1, lbp = -1;
      for (int a = 1, b = 1; a <= la || b <= lb;) {
        if (a <= la && a > lap && A[pL][a].p >= l) {
          if (av >= 0) lav = av, chkmin(res, abs(av - A[pL][a].v));
          av = A[pL][a].v, lap = a;
          if (bv >= 0) chkmin(res, abs(av - bv));
          if (lbv >= 0) chkmin(res, abs(av - lbv));
        }
        if (b <= lb && b > lbp && A[pR][b].p <= r) {
          if (bv >= 0) lbv = bv, chkmin(res, abs(bv - A[pR][b].v));
          bv = A[pR][b].v, lbp = b;
          if (av >= 0) chkmin(res, abs(bv - av));
          if (lav >= 0) chkmin(res, abs(bv - lav));
        }
        A[pL][a].v < A[pR][b].v ? ++a : ++b;
      }
    }
    printf("%d\n", res);
  }
  return 0;
}
