#include <bits/stdc++.h>
using namespace std;
int n, m, a[100010], ans[300010];
vector<pair<int, int> > v[100010];
namespace segment_tree {
int mxval[3300010], ch[3300010][2], nodecnt = 0, rt;
void modify(int &p, int l, int r, int pos, int v) {
  if (!p) p = ++nodecnt;
  if (l == r) {
    mxval[p] = max(mxval[p], v);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(ch[p][0], l, mid, pos, v);
  else
    modify(ch[p][1], mid + 1, r, pos, v);
  mxval[p] = max(mxval[ch[p][0]], mxval[ch[p][1]]);
}
int query(int p, int l, int r, int ql, int qr) {
  if (!p) return 0;
  if (ql > qr) return 0;
  if (ql <= l && r <= qr) return mxval[p];
  int mid = (l + r) >> 1, out = 0;
  if (ql <= mid) out = max(out, query(ch[p][0], l, mid, ql, qr));
  if (qr > mid) out = max(out, query(ch[p][1], mid + 1, r, ql, qr));
  return out;
}
};  // namespace segment_tree
namespace seg2 {
int mn[400010];
void modify2(int p, int l, int r, int ml, int mr, int v) {
  if (ml <= l && r <= mr) {
    mn[p] = min(mn[p], v);
    return;
  }
  int mid = (l + r) >> 1;
  if (ml <= mid) modify2((p << 1), l, mid, ml, mr, v);
  if (mr > mid) modify2((p << 1) | 1, mid + 1, r, ml, mr, v);
}
int query2(int p, int l, int r, int pos) {
  int out = mn[p];
  if (l == r) return out;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    out = min(out, query2((p << 1), l, mid, pos));
  else
    out = min(out, query2((p << 1) | 1, mid + 1, r, pos));
  return out;
}
};  // namespace seg2
using namespace seg2;
using namespace segment_tree;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 1, ti, tj; i <= m; i++) {
    scanf("%d%d", &ti, &tj);
    v[tj].push_back(make_pair(ti, i));
  }
  memset(ans, 0x3f, sizeof(ans));
  for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end());
  memset(mn, 0x3f, sizeof(mn));
  for (int i = 1; i <= n; i++) {
    int prmn, npos = query(rt, 0, 1000000000, 0, a[i]);
    while (npos) {
      prmn = a[i] - a[npos];
      modify2(1, 1, n, 1, npos, prmn);
      int tmp = query(rt, 0, 1000000000, (a[npos] + a[i]) / 2 + 1, a[i]);
      npos = tmp;
    }
    for (int j = 0; j < v[i].size(); j++)
      ans[v[i][j].second] = query2(1, 1, n, v[i][j].first);
    modify(rt, 0, 1000000000, a[i], i);
  }
  memset(mxval, 0, sizeof(mxval));
  memset(ch, 0, sizeof(ch));
  nodecnt = rt = 0;
  for (int i = 1; i <= n; i++) a[i] = 1000000000 - a[i];
  memset(mn, 0x3f, sizeof(mn));
  for (int i = 1; i <= n; i++) {
    int prmn, npos = query(rt, 0, 1000000000, 0, a[i]);
    while (npos) {
      prmn = a[i] - a[npos];
      modify2(1, 1, n, 1, npos, prmn);
      int tmp = query(rt, 0, 1000000000, (a[npos] + a[i]) / 2 + 1, a[i]);
      npos = tmp;
    }
    for (int j = 0; j < v[i].size(); j++)
      ans[v[i][j].second] =
          min(ans[v[i][j].second], query2(1, 1, n, v[i][j].first));
    modify(rt, 0, 1000000000, a[i], i);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
