#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
inline int read() {
  char ch = getchar();
  int res = 0, f = 1;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    res = (res << 3) + (res << 1) + (ch - '0');
  return res * f;
}
const int MAXN = 1e5 + 5, inf = 1e9, MAXM = 3e5 + 5;
int n, a[MAXN], m, mi, res[MAXM];
struct Segment {
  int l, r, ans, mid;
  vector<int> val;
} bet[MAXN * 4];
struct QUERY {
  int l, r, id;
} q[MAXM];
void build(int k, int l, int r) {
  bet[k].l = l, bet[k].r = r, bet[k].ans = inf, bet[k].mid = (l + r) >> 1;
  if (l == r) return bet[k].val.push_back(a[l]), void();
  build((k << 1), l, bet[k].mid), build(((k << 1) | 1), bet[k].mid + 1, r);
  int i = 0, j = 0, x = bet[(k << 1)].val.size(),
      y = bet[((k << 1) | 1)].val.size();
  while (i < x && j < y)
    bet[k].val.push_back(bet[(k << 1)].val[i] < bet[((k << 1) | 1)].val[j]
                             ? bet[(k << 1)].val[i++]
                             : bet[((k << 1) | 1)].val[j++]);
  while (i < x) bet[k].val.push_back(bet[(k << 1)].val[i++]);
  while (j < y) bet[k].val.push_back(bet[((k << 1) | 1)].val[j++]);
}
inline int M_min(int a, int b) { return a < b ? a : b; }
void change(int k, int pos, int x) {
  if (bet[k].r <= pos) {
    vector<int>::iterator it =
        upper_bound(bet[k].val.begin(), bet[k].val.end(), x);
    if (it != bet[k].val.end()) bet[k].ans = M_min(bet[k].ans, *it - x);
    if (it != bet[k].val.begin()) bet[k].ans = M_min(bet[k].ans, x - *(it - 1));
    if (mi <= bet[k].ans) return;
    if (bet[k].l == bet[k].r) return mi = M_min(mi, bet[k].ans), void();
  }
  if (pos > bet[k].mid) change(((k << 1) | 1), pos, x);
  change((k << 1), pos, x);
  bet[k].ans =
      M_min(bet[k].ans, M_min(bet[(k << 1)].ans, bet[((k << 1) | 1)].ans));
  mi = M_min(mi, bet[k].ans);
}
int query(int k, int l, int r) {
  if (bet[k].l > r || bet[k].r < l) return inf;
  if (bet[k].l >= l && bet[k].r <= r) return bet[k].ans;
  return M_min(query((k << 1), l, r), query(((k << 1) | 1), l, r));
}
bool cmp(const QUERY& x, const QUERY& y) { return x.r < y.r; }
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n);
  m = read();
  for (int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].id = i;
  sort(q + 1, q + m + 1, cmp);
  for (int p = 1, i = 2; i <= n; ++i) {
    mi = inf, change(1, i - 1, a[i]);
    for (; p <= m && q[p].r <= i; ++p) res[q[p].id] = query(1, q[p].l, i);
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", res[i]);
  return 0;
}
