#include <bits/stdc++.h>
using namespace std;
int IN() {
  int x = 0, f = 0, ch;
  for (; (ch = getchar()) < '0' || ch > '9';) f = (ch == '-');
  for (; ch >= '0' && ch <= '9'; (ch = getchar())) x = x * 10 + ch - '0';
  return f ? -x : x;
}
int N, M, Q, Q1, Q2, S, T, A[300005], B[300005], ID[300005], Ans[300005];
struct Nod {
  int l, r, ID;
} G1[300005], G2[300005];
namespace Work1 {
int C, D, cnt[300005], pre[300005], suf[300005], ans[300005];
Nod G[300005];
struct Opt {
  int k, x, y;
} H[300005];
bool Cmp1(const Nod& a, const Nod& b) { return a.l < b.l; }
bool Cmp(const Nod& a, const Nod& b) { return a.r > b.r; }
void Del(int x) {
  cnt[x]--;
  if (!cnt[x]) {
    if (pre[x] != 0) {
      H[++D] = (Opt){1, pre[x], suf[pre[x]]};
      suf[pre[x]] = suf[x];
    }
    if (suf[x] != M + 1) {
      H[++D] = (Opt){2, suf[x], pre[suf[x]]};
      pre[suf[x]] = pre[x];
    }
  }
}
int Ask(int x) {
  if (cnt[x]) return 0;
  int ret = (1 << 30);
  if (pre[x] != 0) ret = min(ret, B[x] - B[pre[x]]);
  if (suf[x] != M + 1) ret = min(ret, B[suf[x]] - B[x]);
  return ret;
}
void Cal1(int s, int t) {
  for (int i = 1, lim = M; i <= lim; i++) cnt[i] = 0;
  for (int i = t + 1, lim = N; i <= lim; i++) cnt[A[i]]++;
  for (int i = 1, last = 0; i <= M; i++) {
    pre[i] = last;
    if (cnt[i]) last = i;
  }
  for (int i = M, last = M + 1; i; i--) {
    suf[i] = last;
    if (cnt[i]) last = i;
  }
  D = 0;
  for (int i = N, lim = t + 1; i >= lim; i--) {
    Del(A[i]);
    ans[i] = Ask(A[i]);
  }
  for (int i = t + 2, lim = N; i <= lim; i++) ans[i] = min(ans[i], ans[i - 1]);
  for (int i = 1, lim = C; i <= lim; i++)
    Ans[G[i].ID] = min(Ans[G[i].ID], ans[G[i].r]);
}
void Cal2(int s, int t) {
  for (int i = 1, lim = M; i <= lim; i++) cnt[i] = 0;
  for (int i = s, lim = N; i <= lim; i++) cnt[A[i]]++;
  for (int i = 1, last = 0; i <= M; i++) {
    pre[i] = last;
    if (cnt[i]) last = i;
  }
  for (int i = M, last = M + 1; i; i--) {
    suf[i] = last;
    if (cnt[i]) last = i;
  }
  D = 0;
  for (int i = N, j = 1; i > t; i--) {
    if (G[j].r == i) {
      D = 0;
      for (int k = s, lim = t; k <= lim; k++) {
        Del(A[k]);
        ans[k] = Ask(A[k]);
      }
      for (int k = t - 1, lim = s; k >= lim; k--)
        ans[k] = min(ans[k], ans[k + 1]);
      for (; j <= C && G[j].r == i; j++)
        Ans[G[j].ID] = min(Ans[G[j].ID], ans[G[j].l]);
      for (int k = s, lim = t; k <= lim; k++) cnt[A[k]]++;
      for (; D; D--) {
        if (H[D].k == 1)
          suf[H[D].x] = H[D].y;
        else
          pre[H[D].x] = H[D].y;
      }
    }
    Del(A[i]);
  }
}
void Main() {
  sort(G1 + 1, G1 + Q1 + 1, Cmp1);
  for (int i = 1, j = 1; i < T; i++) {
    int s = (i - 1) * S + 1, t = i * S;
    C = 0;
    for (; j <= Q1 && ID[G1[j].l] == i; j++) G[++C] = G1[j];
    sort(G + 1, G + C + 1, Cmp);
    Cal1(s, t);
    Cal2(s, t);
  }
}
};  // namespace Work1
namespace Work2 {
int F[2][300005];
bool Cmp(const Nod& a, const Nod& b) { return a.r - a.l < b.r - b.l; }
void Main() {
  sort(G2 + 1, G2 + Q2 + 1, Cmp);
  for (int i = 1, lim = N; i <= lim; i++) F[1][i] = (1 << 30);
  for (int i = 2, k = 1; i <= S; i++) {
    int p = i & 1, q = p ^ 1;
    for (int j = 1, lim = N - i + 1; j <= lim; j++)
      F[p][j] = min(F[q][j], min(F[q][j + 1], abs(B[A[j]] - B[A[j + i - 1]])));
    for (; k <= Q2 && G2[k].r - G2[k].l + 1 == i; k++)
      Ans[G2[k].ID] = F[p][G2[k].l];
  }
}
};  // namespace Work2
int main(int argc, char* argv[]) {
  N = IN();
  for (int i = 1, lim = N; i <= lim; i++) A[i] = B[i] = IN();
  sort(B + 1, B + N + 1);
  M = unique(B + 1, B + N + 1) - B - 1;
  for (int i = 1, lim = N; i <= lim; i++)
    A[i] = lower_bound(B + 1, B + M + 1, A[i]) - B;
  S = (int)(sqrt(N) / 2) + 1;
  for (int i = 1, lim = N; i <= lim; i++) ID[i] = (i - 1) / S + 1;
  T = ID[N];
  Q = IN();
  for (int i = 1, lim = Q; i <= lim; i++) {
    int l = IN(), r = IN();
    Ans[i] = (1 << 30);
    if (ID[l] != ID[r])
      G1[++Q1] = (Nod){l, r, i};
    else
      G2[++Q2] = (Nod){l, r, i};
  }
  Work1::Main();
  Work2::Main();
  for (int i = 1, lim = Q; i <= lim; i++) printf("%d\n", Ans[i]);
  return 0;
}
