#include <bits/stdc++.h>
using namespace std;
long long powmod(long long a, long long b, long long p) {
  long long res = 1;
  a %= p;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
  }
  return res;
}
template <typename T>
T gcd(T x, T y) {
  while (y) {
    T t = x % y;
    x = y;
    y = t;
  }
  return x;
}
template <typename T>
T lsM(T x, T y) {
  return x / gcd(x, y) * y;
}
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
set<int> s[120000 << 2];
int a[120000], mi[120000 << 2], n, ans[120000 * 3];
struct query {
  int l, r, id;
  bool operator<(const query &a) const {
    return l == a.l ? (r == a.r ? id < a.id : r < a.r) : l < a.l;
  }
} q[120000 * 3];
void build(int rt, int ll, int rr) {
  mi[rt] = 0x3f3f3f3f;
  for (int i = ll; i <= rr; i++) s[rt].insert(a[i]);
  if (ll == rr) return;
  build((rt << 1), ll, ((ll + rr) / 2));
  build(((rt << 1) | 1), ((ll + rr) / 2) + 1, rr);
}
int query(int rt, int ll, int rr, int l, int r) {
  if (l <= ll && rr <= r) return mi[rt];
  if (r <= ((ll + rr) / 2))
    return query((rt << 1), ll, ((ll + rr) / 2), l, r);
  else if (l > ((ll + rr) / 2))
    return query(((rt << 1) | 1), ((ll + rr) / 2) + 1, rr, l, r);
  else
    return min(query((rt << 1), ll, ((ll + rr) / 2), l, r),
               query(((rt << 1) | 1), ((ll + rr) / 2) + 1, rr, l, r));
}
void update(int rt, int ll, int rr, int l, int r, int v, int &x) {
  if (ll > r || rr < l) return;
  if (ll == rr) {
    mi[rt] = min(mi[rt], abs(v - a[ll]));
    x = min(x, mi[rt]);
    return;
  }
  auto k = s[rt].lower_bound(v);
  if ((k == s[rt].end() || *k - v >= x) &&
      (k == s[rt].begin() || v - *(--k) >= x)) {
    x = min(x, query(rt, ll, rr, l, r));
    return;
  }
  if (l <= ((ll + rr) / 2)) update((rt << 1), ll, ((ll + rr) / 2), l, r, v, x);
  if (r > ((ll + rr) / 2))
    update(((rt << 1) | 1), ((ll + rr) / 2) + 1, rr, l, r, v, x);
  mi[rt] = min(mi[(rt << 1)], mi[((rt << 1) | 1)]);
  return;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[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);
  build(1, 1, n);
  for (int i = m, j = n; i >= 1; i--) {
    while (j >= q[i].l) {
      int x = 0x3f3f3f3f;
      update(1, 1, n, j + 1, n, a[j], x);
      j--;
    }
    ans[q[i].id] = query(1, 1, n, q[i].l, q[i].r);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
