#include <bits/stdc++.h>
using namespace std;
struct bb {
  int l, r, id;
} b[300010];
struct tt {
  int l, r, mx, mn;
} t[4000010];
int n, m, w[300010], ans[300010], l, root[300010], x, now;
vector<int> d1[300010], d2[300010];
inline char gc() {
  static char now[1 << 16], *S, *T;
  if (S == T) {
    T = (S = now) + fread(now, 1, 1 << 16, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
inline int read() {
  int x = 0, f = 1;
  char ch = gc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = gc();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = gc();
  }
  return x * f;
}
inline bool cmp(bb a, bb b) { return a.r < b.r; }
inline void ins(int i, int x, int y, int L, int R) {
  t[l] = t[i];
  t[l].mx = max(t[l].mx, y);
  if (L < R) {
    int mid = (L + R) >> 1, l1 = l;
    if (x <= mid) {
      l++;
      t[l1].l = l;
      ins(t[i].l, x, y, L, mid);
    } else {
      l++;
      t[l1].r = l;
      ins(t[i].r, x, y, mid + 1, R);
    }
  }
}
inline int cmx(int i, int a, int b, int L, int R) {
  if (a <= L && R <= b) return t[i].mx;
  int mid = (L + R) >> 1, mx = 0;
  if (a <= mid) mx = max(mx, cmx(t[i].l, a, b, L, mid));
  if (mid < b) mx = max(mx, cmx(t[i].r, a, b, mid + 1, R));
  return mx;
}
inline void maketree(int L, int R) {
  t[l].l = t[l].r = 0;
  t[l].mn = 2147483647;
  if (L < R) {
    int mid = (L + R) >> 1, l1 = l;
    l++;
    t[l1].l = l;
    maketree(L, mid);
    l++;
    t[l1].r = l;
    maketree(mid + 1, R);
  }
}
inline void ins1(int i, int x, int y, int L, int R) {
  if (L == R) {
    t[i].mn = min(t[i].mn, y);
    return;
  }
  int mid = (L + R) >> 1;
  if (x <= mid)
    ins1(t[i].l, x, y, L, mid);
  else
    ins1(t[i].r, x, y, mid + 1, R);
  t[i].mn = min(t[t[i].l].mn, t[t[i].r].mn);
}
inline int cmn(int i, int a, int b, int L, int R) {
  if (a <= L && R <= b) return t[i].mn;
  int mid = (L + R) >> 1, mn = 2147483647;
  if (a <= mid) mn = min(mn, cmn(t[i].l, a, b, L, mid));
  if (mid < b) mn = min(mn, cmn(t[i].r, a, b, mid + 1, R));
  return mn;
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) w[i] = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    b[i].l = read();
    b[i].r = read();
    b[i].id = i;
  }
  sort(b + 1, b + 1 + m, cmp);
  l = root[0] = 0;
  t[0].l = t[0].r = t[0].mx = 0;
  for (int i = 1; i <= n; i++) {
    d1[i].clear();
    d2[i].clear();
    x = cmx(root[i - 1], w[i], 1000000000, 0, 1000000000);
    while (x) {
      d1[i].push_back(x);
      if (w[i] > (w[i] + w[x] - 1) / 2) break;
      x = cmx(root[x - 1], w[i], (w[i] + w[x] - 1) / 2, 0, 1000000000);
    }
    x = cmx(root[i - 1], 1, w[i], 0, 1000000000);
    while (x) {
      d2[i].push_back(x);
      if ((w[x] + w[i]) / 2 + 1 > w[i]) break;
      x = cmx(root[x - 1], (w[x] + w[i]) / 2 + 1, w[i], 0, 1000000000);
    }
    l++;
    root[i] = l;
    ins(root[i - 1], w[i], i, 0, 1000000000);
  }
  l = 1;
  maketree(1, n);
  now = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < d1[i].size(); j++)
      ins1(1, d1[i][j], w[d1[i][j]] - w[i], 1, n);
    for (int j = 0; j < d2[i].size(); j++)
      ins1(1, d2[i][j], w[i] - w[d2[i][j]], 1, n);
    while (now < m && b[now + 1].r == i) {
      now++;
      ans[b[now].id] = cmn(1, b[now].l, b[now].r, 1, n);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
