#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = 0;
  int x = 0, flag = 1;
  while (!isdigit(ch)) {
    ch = getchar();
    if (ch == '-') flag = -1;
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * flag;
}
struct President_Tree {
  int size, lc[3300000], rc[3300000], sumv[3300000];
  void pushup(int o) { sumv[o] = sumv[lc[o]] + sumv[rc[o]]; }
  void optset(int &o, int p, int l, int r, int q) {
    if (!o) o = ++size;
    if (l == r) {
      sumv[o]++;
      return;
    }
    if (q <= ((l + r) >> 1))
      optset(lc[o], lc[p], l, ((l + r) >> 1), q), rc[o] = rc[p];
    else
      optset(rc[o], rc[p], ((l + r) >> 1) + 1, r, q), lc[o] = lc[p];
    pushup(o);
  }
  int solve(int o, int p, int l, int r) {
    if (l == r) return l;
    if (sumv[lc[o]] - sumv[lc[p]])
      return solve(lc[o], lc[p], l, ((l + r) >> 1));
    else
      return solve(rc[o], rc[p], ((l + r) >> 1) + 1, r);
  }
  int query(int o, int p, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) {
      if (sumv[o] - sumv[p])
        return solve(o, p, l, r);
      else
        return 0;
    }
    int ans = 0;
    if (ql <= ((l + r) >> 1))
      ans = query(lc[o], lc[p], l, ((l + r) >> 1), ql, qr);
    if (ans) return ans;
    if (qr > ((l + r) >> 1))
      ans = query(rc[o], rc[p], ((l + r) >> 1) + 1, r, ql, qr);
    if (ans) return ans;
    return ans;
  }
} T;
struct Segment_Tree {
  int minv[330000 * 4];
  inline void pushup(int o) { minv[o] = min(minv[o << 1], minv[o << 1 | 1]); }
  void build(int o, int l, int r) {
    minv[o] = +1e9 + 7;
    if (l == r) return;
    build(o << 1, l, ((l + r) >> 1));
    build(o << 1 | 1, ((l + r) >> 1) + 1, r);
  }
  void optset(int o, int l, int r, int q, int k) {
    if (l == r) {
      minv[o] = min(minv[o], k);
      return;
    }
    if (q <= ((l + r) >> 1))
      optset(o << 1, l, ((l + r) >> 1), q, k);
    else
      optset(o << 1 | 1, ((l + r) >> 1) + 1, r, q, k);
    pushup(o);
  }
  int query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return minv[o];
    int ans = 1e9 + 7;
    if (ql <= ((l + r) >> 1))
      ans = min(ans, query(o << 1, l, ((l + r) >> 1), ql, qr));
    if (qr > ((l + r) >> 1))
      ans = min(ans, query(o << 1 | 1, ((l + r) >> 1) + 1, r, ql, qr));
    return ans;
  }
} H;
int n, m, cnt, a[330000], f[330000], rt[330000], ans[330000];
bool cmp(int x, int y) { return a[x] < a[y]; };
struct node {
  int l, r, k;
} p[330000];
bool cmp_(node a, node b) { return a.l > b.l; }
int get(int x) {
  int l = 0, r = n, mid;
  while (l < r) {
    mid = ((l + r) >> 1) + 1;
    if (a[f[mid]] <= x)
      l = mid;
    else
      r = mid - 1;
  }
  return rt[l];
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), f[i] = i;
  sort(f + 1, f + n + 1, cmp);
  for (int i = 1; i <= n; i++) T.optset(rt[i], rt[i - 1], 1, n, f[i]);
  m = read();
  H.build(1, 1, n);
  for (int i = 1; i <= m; i++) p[i].l = read(), p[i].r = read(), p[i].k = i;
  sort(p + 1, p + m + 1, cmp_);
  for (int i = n, j = 0; i >= 1; i--) {
    int x, ql, qr, tt;
    x = i;
    ql = a[i];
    qr = +1e9 + 7;
    tt = get(ql - 1);
    while (x < n && ql <= qr) {
      x = T.query(get(qr), tt, 1, n, x + 1, n);
      if (x == 0) break;
      H.optset(1, 1, n, x, abs(a[i] - a[x]));
      if (ql == qr) break;
      qr = (ql + a[x]) / 2;
    }
    x = i;
    ql = 0;
    qr = a[i] - 1;
    tt = get(qr);
    while (x < n && ql <= qr) {
      x = T.query(tt, get(ql - 1), 1, n, x + 1, n);
      if (x == 0) break;
      H.optset(1, 1, n, x, abs(a[i] - a[x]));
      if (ql == qr) break;
      ql = (a[x] + qr) / 2;
    }
    while (j != m && p[j + 1].l == i)
      j++, ans[p[j].k] = H.query(1, 1, n, p[j].l, p[j].r);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
