#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 1000;
const int inf = 1e9 + 100;
int a[maxn];
struct Query {
  int l, r, idx, ans;
} q[maxn];
int last;
struct segment_tree {
  vector<int>::iterator it1, it2;
  int rt[maxn * 4], mi[maxn * 4];
  vector<int> ele[maxn * 4];
  void push_up(int rt) { mi[rt] = min(mi[(rt << 1)], mi[(rt << 1 | 1)]); }
  void build(int l, int r, int rt) {
    for (int i = (l), iend = (r); i <= iend; i++) ele[rt].push_back(a[i]);
    sort(ele[rt].begin(), ele[rt].end());
    if (l == r) {
      mi[rt] = inf;
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, (rt << 1));
    build(mid + 1, r, (rt << 1 | 1));
    push_up(rt);
  }
  int get(int rt, int val) {
    int cha = inf;
    it2 = lower_bound(ele[rt].begin(), ele[rt].end(), val);
    it1 = ele[rt].end();
    if (it2 != ele[rt].begin()) it1 = it2, it1--;
    if (it2 != ele[rt].end()) cha = min(cha, abs(val - *it2));
    if (it1 != ele[rt].end()) cha = min(cha, abs(val - *it1));
    return cha;
  }
  void addr(int l, int r, int rt, int tl, int tr, int val) {
    int gg = get(rt, val);
    if (gg >= last) return;
    if (l == r) {
      last = gg;
      mi[rt] = min(mi[rt], last);
      return;
    }
    int mid = (l + r) >> 1;
    if (tr >= mid + 1) addr(mid + 1, r, (rt << 1 | 1), tl, tr, val);
    if (tl <= mid) addr(l, mid, (rt << 1), tl, tr, val);
    push_up(rt);
  }
  int query(int l, int r, int rt, int tl, int tr) {
    if (tl <= l && r <= tr) return mi[rt];
    int mid = (l + r) >> 1;
    int ans = inf;
    if (tl <= mid) ans = min(ans, query(l, mid, (rt << 1), tl, tr));
    if (tr >= mid + 1) ans = min(ans, query(mid + 1, r, (rt << 1 | 1), tl, tr));
    return ans;
  }
} t;
bool cmp1(Query a, Query b) { return a.r < b.r; }
bool cmp2(Query a, Query b) { return a.idx < b.idx; }
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = (1), iend = (n); i <= iend; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = (1), iend = (m); i <= iend; i++)
    scanf("%d%d", &q[i].l, &q[i].r), q[i].idx = i;
  sort(q + 1, q + 1 + m, cmp1);
  t.build(1, n, 1);
  int r = 1;
  for (int i = (1), iend = (m); i <= iend; i++) {
    while (r < q[i].r) last = inf, t.addr(1, n, 1, 1, r, a[r + 1]), r++;
    q[i].ans = t.query(1, n, 1, q[i].l, q[i].r - 1);
  }
  sort(q + 1, q + 1 + m, cmp2);
  for (int i = (1), iend = (m); i <= iend; i++) printf("%d\n", q[i].ans);
  return 0;
}
