#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const int MAXN = 100011;
const int inf = (1 << 30) - 1;
int n, m, val[MAXN];
int A[MAXN * 3];
struct node {
  vector<int> w;
  int ans;
} a[MAXN * 3];
struct ask {
  int l, r, id;
} q[MAXN * 3];
inline int getint() {
  int w = 0, q = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 1, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? -w : w;
}
inline void upd(int &x, int y) {
  if (y < x) x = y;
}
inline bool cmp(ask q, ask qq) { return q.r < qq.r; }
inline void build(int root, int l, int r) {
  if (l == r) {
    a[root].w.push_back(val[l]);
    a[root].ans = inf;
    return;
  }
  int mid = (l + r) >> 1;
  build(root << 1, l, mid);
  build(root << 1 | 1, mid + 1, r);
  int head = 0, s1 = a[root << 1].w.size(), s2 = a[root << 1 | 1].w.size();
  for (int i = 0; i < s1; i++) {
    while (head < s2 && a[root << 1 | 1].w[head] <= a[root << 1].w[i])
      a[root].w.push_back(a[root << 1 | 1].w[head]), head++;
    a[root].w.push_back(a[root << 1].w[i]);
  }
  while (head < s2) a[root].w.push_back(a[root << 1 | 1].w[head]), head++;
  a[root].ans = min(a[root << 1].ans, a[root << 1 | 1].ans);
  for (int i = 1; i <= r - l; i++)
    upd(a[root].ans, a[root].w[i] - a[root].w[i - 1]);
}
inline int query(int root, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return a[root].ans;
  int mid = (l + r) >> 1;
  if (ql > mid)
    return query(root << 1 | 1, mid + 1, r, ql, qr);
  else if (qr <= mid)
    return query(root << 1, l, mid, ql, qr);
  else
    return min(query(root << 1, l, mid, ql, qr),
               query(root << 1 | 1, mid + 1, r, ql, qr));
}
inline void modify(int root, int l, int r, int pos, int vv, int &nowans) {
  if (l == r) {
    upd(nowans, abs(a[root].w[0] - vv));
    upd(a[root].ans, nowans);
    return;
  }
  vector<int>::iterator it =
      lower_bound(a[root].w.begin(), a[root].w.end(), vv);
  if ((it == a[root].w.end() || *it >= vv + nowans) &&
      (it == a[root].w.begin() || *(it - 1) <= vv - nowans)) {
    upd(nowans, query(root, l, r, l, pos));
    return;
  }
  int mid = (l + r) >> 1;
  if (pos > mid)
    modify(root << 1 | 1, mid + 1, r, pos, vv, nowans),
        modify(root << 1, l, mid, pos, vv, nowans);
  else
    modify(root << 1, l, mid, pos, vv, nowans);
  a[root].ans = min(a[root].ans, min(a[root << 1].ans, a[root << 1 | 1].ans));
}
inline void work() {
  n = getint();
  for (int i = 1; i <= n; i++) val[i] = getint();
  build(1, 1, n);
  m = getint();
  for (int i = 1; i <= m; i++)
    q[i].l = getint(), q[i].r = getint(), q[i].id = i;
  sort(q + 1, q + m + 1, cmp);
  int now = 1, minl;
  for (int o = 1; o <= m; o++) {
    while (now < q[o].r)
      minl = inf, modify(1, 1, n, now, val[now + 1], minl), now++;
    A[q[o].id] = query(1, 1, n, q[o].l, q[o].r);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", A[i]);
}
int main() {
  work();
  return 0;
}
