#include <bits/stdc++.h>
using namespace std;
const long long maxn = 3e6 + 100;
const long long inf = 0x3f3f3f3f;
const long long iinf = 1 << 30;
const long long linf = 2e18;
const long long mod = 998244353;
const double eps = 1e-7;
template <class T = long long>
T chmin(T &a, T b) {
  return a = min(a, b);
}
template <class T = long long>
T chmax(T &a, T b) {
  return a = max(a, b);
}
template <class T = long long>
inline void red(T &x) {
  x -= mod, x += x >> 31 & mod;
}
template <class T = long long>
T read() {
  T f = 1, a = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    a = (a << 3) + (a << 1) + ch - '0';
    ch = getchar();
  }
  return a * f;
}
long long n, q, w = 1e9;
long long a[maxn];
vector<pair<long long, long long> > b[maxn];
long long rt, cnt;
struct node {
  long long ls, rs, val;
  void clear() { ls = rs = val = 0; }
} tr[maxn];
void modify(long long &tot, long long l, long long r, long long p,
            long long x) {
  if (!tot) tot = ++cnt, assert(cnt < maxn), tr[tot].clear();
  chmax(tr[tot].val, x);
  if (l == r) return;
  if (p <= ((l + r) >> 1))
    modify(tr[tot].ls, l, ((l + r) >> 1), p, x);
  else
    modify(tr[tot].rs, ((l + r) >> 1) + 1, r, p, x);
}
long long query(long long tot, long long l, long long r, long long L,
                long long R) {
  if (!tot) return 0;
  if (l >= L && r <= R) return tr[tot].val;
  long long ret = 0;
  if (L <= ((l + r) >> 1))
    chmax(ret, query(tr[tot].ls, l, ((l + r) >> 1), L, R));
  if (R > ((l + r) >> 1))
    chmax(ret, query(tr[tot].rs, ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
struct binary_indexed_tree {
  long long val[maxn];
  void init() {
    for (long long i = (1); i <= (n); ++i) val[i] = linf;
  }
  void add(long long pos, long long x) {
    for (long long i = pos; i <= n; i += (i & -i)) chmin(val[i], x);
  }
  long long query(long long pos) {
    long long ret = linf;
    for (long long i = pos; i; i -= (i & -i)) chmin(ret, val[i]);
    return ret;
  }
} bit;
long long ans[maxn];
signed main() {
  n = read();
  for (long long i = (1); i <= (n); ++i) a[i] = read();
  q = read();
  for (long long i = (1); i <= (q); ++i) {
    long long l = read(), r = read();
    b[r].push_back(make_pair(l, i));
    ans[i] = linf;
  }
  bit.init();
  for (long long i = (1); i <= (n); ++i) {
    if (i % 1000 == 0) cerr << i << endl;
    long long pos = query(rt, 1, w, 1, a[i]);
    while (pos) {
      bit.add(n - pos + 1, a[i] - a[pos]);
      if (a[pos] == a[i]) break;
      pos = query(rt, 1, w, a[i] - (a[i] - a[pos]) / 2, a[i]);
    }
    for (pair<long long, long long> j : b[i])
      chmin(ans[j.second], bit.query(n - j.first + 1));
    modify(rt, 1, w, a[i], i);
  }
  bit.init();
  rt = cnt = 0;
  for (long long i = (1); i <= (n); ++i) {
    long long pos = query(rt, 1, w, a[i], w);
    while (pos) {
      bit.add(n - pos + 1, a[pos] - a[i]);
      if (a[pos] == a[i]) break;
      pos = query(rt, 1, w, a[i], a[i] + (a[pos] - a[i]) / 2);
    }
    for (pair<long long, long long> j : b[i])
      chmin(ans[j.second], bit.query(n - j.first + 1));
    modify(rt, 1, w, a[i], i);
  }
  for (long long i = (1); i <= (q); ++i) printf("%lld\n", ans[i]);
  return 0;
}
