#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, m, *a[maxn << 2], b[maxn], mn[maxn << 2], pool[maxn * 18], *pre = pool;
struct data {
  int l, r, id;
  void ini(int x) {
    id = x;
    scanf("%d%d", &l, &r);
  }
  bool operator<(const data &a) const { return r < a.r; }
} d[3 * maxn];
int res[3 * maxn];
int rlm, rmn;
void Min(int &x, int y) {
  if (x > y) x = y;
}
void build(int x, int l, int r) {
  mn[x] = 1 << 30;
  if (l == r) return;
  int sz = r - l + 1, i, mid = (l + r) >> 1;
  a[x] = pre;
  pre += sz;
  for (i = 0; i < sz; i++) a[x][i] = b[i + l];
  sort(a[x], a[x] + sz);
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}
void upd(int x, int l, int r) {
  if (l == r) {
    Min(mn[x], abs(b[rlm] - b[l])), Min(rmn, mn[x]);
    return;
  }
  if (r < rlm) {
    int *pos = lower_bound(a[x], a[x] + r - l + 1, b[rlm]);
    if ((pos == a[x] || b[rlm] >= *(pos - 1) + rmn) &&
        (pos == a[x] + r - l + 1 || b[rlm] <= *pos - rmn)) {
      Min(rmn, mn[x]);
      return;
    }
  }
  int mid = (l + r) >> 1;
  if (rlm - 1 > mid) upd(x << 1 | 1, mid + 1, r);
  upd(x << 1, l, mid);
  mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
int cal(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return mn[x];
  int mid = (l + r) >> 1, res = 1 << 30;
  if (L <= mid) Min(res, cal(x << 1, l, mid, L, R));
  if (R > mid) Min(res, cal(x << 1 | 1, mid + 1, r, L, R));
  return res;
}
int main() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", b + i);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) d[i].ini(i);
  sort(d + 1, d + m + 1);
  build(1, 1, n);
  for (rlm = i = 1; i <= m; i++) {
    while (rlm < d[i].r) {
      ++rlm;
      rmn = 1 << 30;
      upd(1, 1, n);
    }
    res[d[i].id] = cal(1, 1, n, d[i].l, d[i].r - 1);
  }
  for (i = 1; i <= m; i++) printf("%d\n", res[i]);
  return 0;
}
