#include <bits/stdc++.h>
const int N = 1000000 + 233;
const long long INF = 1ll << 62;
int n, q;
long long w[N], res[N << 2], mini, ans[N];
std::vector<long long> t[N << 2];
struct Interval {
  int l, r, id;
  friend bool operator<(Interval x, Interval y) { return x.r < y.r; }
} ask[N];
void build(int p, int l, int r) {
  for (int i = l; i <= r; ++i) t[p].push_back(w[i]);
  std::sort(t[p].begin(), t[p].end());
  res[p] = INF;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
}
void modify(int p, int l, int r, int x, long long d) {
  if (r <= x) {
    std::vector<long long>::iterator it =
        std::lower_bound(t[p].begin(), t[p].end(), d);
    if (it != t[p].end()) res[p] = std::min(res[p], *it - d);
    if (it != t[p].begin()) res[p] = std::min(res[p], d - *(it - 1));
    if (mini <= res[p]) return;
    if (l == r) return (void)(mini = std::min(mini, res[p]));
  }
  int mid = (l + r) >> 1;
  if (x > mid) modify(p << 1 | 1, mid + 1, r, x, d);
  modify(p << 1, l, mid, x, d);
  res[p] = std::min(res[p], std::min(res[p << 1], res[p << 1 | 1]));
  mini = std::min(mini, res[p]);
}
long long query(int p, int l, int r, int pl, int pr) {
  if (l >= pl && r <= pr) return res[p];
  int mid = (l + r) >> 1;
  long long ret = INF;
  if (pl <= mid) ret = std::min(ret, query(p << 1, l, mid, pl, pr));
  if (pr > mid) ret = std::min(ret, query(p << 1 | 1, mid + 1, r, pl, pr));
  return ret;
}
signed main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%lld", w + i);
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d", &ask[i].l, &ask[i].r);
    ask[i].id = i;
  }
  std::sort(ask + 1, ask + 1 + q);
  build(1, 1, n);
  for (int i = 2, ptr = 1; i <= n; ++i) {
    mini = INF;
    modify(1, 1, n, i - 1, w[i]);
    while (ptr <= q && ask[ptr].r <= i) {
      ans[ask[ptr].id] = query(1, 1, n, ask[ptr].l, i);
      ++ptr;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
  return 0;
}
