#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Node {
  int l, r, mi;
  set<int> s;
} a[N << 2];
int t[N];
struct Query {
  int l, r, id;
} q[N * 3];
inline bool cmp(const Query& q, const Query& w) {
  if (q.l != w.l) return q.l < w.l;
  if (q.r != w.r) return q.r < w.r;
  return q.id < w.id;
}
void Buildtree(int i, int l, int r) {
  a[i].l = l;
  a[i].r = r;
  a[i].mi = 0x3f3f3f3f;
  for (int q = l; q <= r; q++) a[i].s.insert(t[q]);
  if (l == r) return;
  int mid = l + r >> 1;
  Buildtree(i << 1, l, mid);
  Buildtree(i << 1 | 1, mid + 1, r);
}
int query(int i, int l, int r) {
  if (l <= a[i].l && a[i].r <= r) return a[i].mi;
  int mid = a[i].l + a[i].r >> 1;
  if (r <= mid)
    return query(i << 1, l, r);
  else if (l > mid)
    return query(i << 1 | 1, l, r);
  else
    return min(query(i << 1, l, r), query(i << 1 | 1, l, r));
}
void update(int i, int l, int r, int v, int& mi) {
  if (a[i].l > r || a[i].r < l) return;
  if (a[i].l == a[i].r) {
    a[i].mi = min(a[i].mi, abs(v - t[a[i].l]));
    mi = min(mi, a[i].mi);
    return;
  }
  set<int>& T = a[i].s;
  auto k = T.lower_bound(v);
  if ((k == T.end() || (*k - v) >= mi) &&
      (k == T.begin() || (v - *(--k)) >= mi)) {
    mi = min(mi, query(i, l, r));
    return;
  }
  if (a[i << 1].r >= l) update(i << 1, l, r, v, mi);
  if (a[i << 1 | 1].l <= r) update(i << 1 | 1, l, r, v, mi);
  a[i].mi = min(a[i << 1].mi, a[i << 1 | 1].mi);
}
int ans[N * 3];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
  int m;
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) scanf("%d %d", &q[i].l, &q[i].r), q[i].id = i;
  sort(q + 1, q + 1 + m, cmp);
  Buildtree(1, 1, n);
  for (int i = m, j = n; i >= 1; i--) {
    for (; j >= q[i].l; j--) {
      int ct = 0x3f3f3f3f;
      update(1, j + 1, n, t[j], ct);
    }
    ans[q[i].id] = query(1, q[i].l, q[i].r);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
