#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int n, m, q;
int s[N * 50], ch[N * 50][2], rt[N], tt;
void inst(int o1, int o2, int x, int y) {
  s[o1] = max(s[o2], y);
  int l = 1, r = m;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (x <= mid) {
      ch[o1][0] = ++tt, ch[o1][1] = ch[o2][1];
      o1 = ch[o1][0], o2 = ch[o2][0];
      r = mid;
    } else {
      ch[o1][0] = ch[o2][0], ch[o1][1] = ++tt;
      o1 = ch[o1][1], o2 = ch[o2][1];
      l = mid + 1;
    }
    s[o1] = max(s[o2], y);
  }
}
int quer(int o, int l, int r, int ll, int rr) {
  if (!o || ll > rr) return 0;
  if (ll <= l && r <= rr) return s[o];
  int an = 0, mid = (l + r) >> 1;
  if (ll <= mid) an = max(an, quer(ch[o][0], l, mid, ll, rr));
  if (rr > mid) an = max(an, quer(ch[o][1], mid + 1, r, ll, rr));
  return an;
}
int mi[N << 2];
void psup(int o) { mi[o] = min(mi[o << 1], mi[o << 1 | 1]); }
void modif(int o, int l, int r, int lx, int x) {
  if (l == r) {
    mi[o] = min(mi[o], x);
    return;
  }
  int mid = (l + r) >> 1;
  if (lx <= mid)
    modif(o << 1, l, mid, lx, x);
  else
    modif(o << 1 | 1, mid + 1, r, lx, x);
  psup(o);
}
int q2(int o, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) return mi[o];
  int an = 1 << 30, mid = (l + r) >> 1;
  if (ll <= mid) an = min(an, q2(o << 1, l, mid, ll, rr));
  if (rr > mid) an = min(an, q2(o << 1 | 1, mid + 1, r, ll, rr));
  return an;
}
int a[N], b[N], an[N];
struct QR {
  int l, r, i;
  bool operator<(const QR &bb) const { return r < bb.r; }
} qq[N];
void wk() {
  while (tt) {
    s[tt] = ch[tt][0] = ch[tt][1] = 0;
    --tt;
  }
  memset(mi, 0x3f3f3f, sizeof(mi));
  for (int i = 1; i <= n; ++i) inst(rt[i] = ++tt, rt[i - 1], a[i], i);
  for (int i = 1, j = 1; i <= n; ++i) {
    int mx = 1 << 30, pp = i - 1;
    while (1) {
      int rr = upper_bound(b + 1, b + m + 1, mx) - b - 1,
          k = quer(rt[pp], 1, m, a[i], rr);
      if (!k) break;
      pp = k - 1;
      mx = b[a[k]];
      modif(1, 1, n, k, mx - b[a[i]]);
      if (mx == b[a[i]]) break;
      mx = (mx - b[a[i]] == 1) ? b[a[i]] : mx - (mx - b[a[i]]) / 2;
    }
    while (j <= q && qq[j].r == i) {
      an[qq[j].i] = min(an[qq[j].i], q2(1, 1, n, qq[j].l, qq[j].r));
      ++j;
    }
  }
}
int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) a[i] = b[i] = rd();
  sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1;
  b[++m] = 1 << 30 | 1;
  for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
  q = rd();
  for (int i = 1; i <= q; ++i) {
    an[i] = 1 << 30;
    qq[i].l = rd(), qq[i].r = rd(), qq[i].i = i;
  }
  sort(qq + 1, qq + q + 1);
  wk();
  reverse(a + 1, a + n + 1);
  for (int i = 1; i <= q; ++i) {
    qq[i].l = n - qq[i].l + 1, qq[i].r = n - qq[i].r + 1;
    swap(qq[i].l, qq[i].r);
  }
  sort(qq + 1, qq + q + 1);
  wk();
  for (int i = 1; i <= q; ++i) printf("%d\n", an[i]);
  return 0;
}
