#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 3e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, num[maxn], ans[maxm], l, r;
vector<int> qs[maxn], id[maxn];
namespace SGT {
const int L = 0, R = 1;
struct node {
  int mn, ch[2];
} t[maxn << 1];
int root, cnt;
int dat[23][maxn];
void push_up(int rt) {
  t[rt].mn = min(t[rt].mn, min(t[t[rt].ch[L]].mn, t[t[rt].ch[R]].mn));
}
void merge(int ly, int l, int r) {
  int mid = l + r >> 1;
  int lp = l, rp = mid + 1, tot = l;
  while (lp <= mid && rp <= r)
    if (dat[ly + 1][lp] < dat[ly + 1][rp])
      dat[ly][tot++] = dat[ly + 1][lp++];
    else
      dat[ly][tot++] = dat[ly + 1][rp++];
  while (lp <= mid) dat[ly][tot++] = dat[ly + 1][lp++];
  while (rp <= r) dat[ly][tot++] = dat[ly + 1][rp++];
}
void build(int ly, int l, int r, int& rt) {
  rt = ++cnt, t[rt].mn = inf;
  if (l == r) return dat[ly][l] = num[l], void();
  int mid = l + r >> 1;
  build(ly + 1, l, mid, t[rt].ch[L]);
  build(ly + 1, mid + 1, r, t[rt].ch[R]);
  merge(ly, l, r);
  for (register int i = 1; i <= r - l; ++i)
    t[rt].mn = min(t[rt].mn, dat[ly][l + i] - dat[ly][l + i - 1]);
  push_up(rt);
}
int query(int l, int r, int tl, int tr, int rt) {
  if (l == tl && r == tr) return t[rt].mn;
  int mid = tl + tr >> 1;
  if (r <= mid)
    return query(l, r, tl, mid, t[rt].ch[L]);
  else if (l > mid)
    return query(l, r, mid + 1, tr, t[rt].ch[R]);
  else
    return min(query(l, mid, tl, mid, t[rt].ch[L]),
               query(mid + 1, r, mid + 1, tr, t[rt].ch[R]));
}
void ins(int ly, int r, int tl, int tr, int dt, int& mn, int rt) {
  if (tl == tr) {
    t[rt].mn = min(t[rt].mn, abs(num[tl] - dt));
    mn = min(t[rt].mn, mn);
    return;
  }
  int mid = tl + tr >> 1;
  int pos = lower_bound(dat[ly] + tl, dat[ly] + tr + 1, dt) - dat[ly];
  int pre = dat[ly][pos - 1], suc = dat[ly][pos];
  if ((pos == tr + 1 || dt + mn <= suc) && (pos == tl || dt - mn >= pre)) {
    mn = min(mn, t[rt].mn);
    return;
  }
  if (r <= mid)
    ins(ly + 1, r, tl, mid, dt, mn, t[rt].ch[L]);
  else
    ins(ly + 1, r, mid + 1, tr, dt, mn, t[rt].ch[R]),
        ins(ly + 1, mid, tl, mid, dt, mn, t[rt].ch[L]);
  push_up(rt);
}
}  // namespace SGT
int main() {
  scanf("%d", &n);
  for (register int i = 1; i <= n; ++i) scanf("%d", &num[i]);
  scanf("%d", &m);
  for (register int i = 1; i <= m; ++i) {
    scanf("%d%d", &l, &r);
    qs[r].push_back(l);
    id[r].push_back(i);
  }
  SGT::build(0, 1, n, SGT::root);
  int mn = inf;
  for (register int i = 2; i <= n; ++i) {
    mn = inf;
    SGT::ins(0, i - 1, 1, n, num[i], mn, 1);
    for (register int j = qs[i].size() - 1; j >= 0; --j) {
      ans[id[i][j]] = SGT::query(qs[i][j], i, 1, n, 1);
    }
  }
  for (register int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
