#include <bits/stdc++.h>
using namespace std;
int n;
int a[100100];
int m;
struct Que {
  int l, r, id;
  bool operator<(const Que &o) const { return r < o.r; }
} que[300300];
int ans[300300];
int M = 0x3f3f3f3f;
struct SEG {
  vector<int> val[500500];
  int mi[500500];
  void build(int rt, int l, int r) {
    for (int i = l; i <= r; ++i) val[rt].push_back(a[i]);
    sort(val[rt].begin(), val[rt].end());
    mi[rt] = 0x3f3f3f3f;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(rt * 2, l, mid);
    build(rt * 2 + 1, mid + 1, r);
  }
  void change(int rt, int l, int r, int ed, int x) {
    if (r <= ed) {
      vector<int>::iterator p = upper_bound(val[rt].begin(), val[rt].end(), x);
      if (p != val[rt].end()) mi[rt] = min(mi[rt], *p - x);
      if (p != val[rt].begin()) mi[rt] = min(mi[rt], x - *(p - 1));
      if (mi[rt] >= M) return;
      if (l == r) {
        M = min(M, mi[rt]);
        return;
      }
    }
    int mid = (l + r) / 2;
    if (mid < ed) change(rt * 2 + 1, mid + 1, r, ed, x);
    change(rt * 2, l, mid, ed, x);
    mi[rt] = min(mi[rt], min(mi[rt * 2], mi[rt * 2 + 1]));
    M = min(M, mi[rt]);
  }
  int ask(int rt, int l, int r, int st, int ed) {
    if (l > ed || r < st) return 0x3f3f3f3f;
    if (l >= st && r <= ed) return mi[rt];
    int mid = (l + r) / 2;
    return min(ask(rt * 2, l, mid, st, ed),
               ask(rt * 2 + 1, mid + 1, r, st, ed));
  }
} seg;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  seg.build(1, 1, n);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i)
    scanf("%d%d", &que[i].l, &que[i].r), que[i].id = i;
  sort(que + 1, que + m + 1);
  int p = 1;
  for (int i = 2; i <= n; ++i) {
    M = 0x3f3f3f3f;
    seg.change(1, 1, n, i - 1, a[i]);
    while (p <= m && que[p].r == i)
      ans[que[p].id] = seg.ask(1, 1, n, que[p].l, i), p++;
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
