#include <bits/stdc++.h>
using namespace std;
using LL = long long;
namespace _buff {
const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
  if (ib == ie) {
    ib = ibuf;
    ie = ibuf + fread(ibuf, 1, BUFF, stdin);
  }
  return ib == ie ? -1 : *ib++;
}
}  // namespace _buff
LL read() {
  using namespace _buff;
  LL ret = 0;
  bool pos = true;
  char c = getc();
  for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
    assert(~c);
  }
  if (c == '-') {
    pos = false;
    c = getc();
  }
  for (; c >= '0' && c <= '9'; c = getc()) {
    ret = (ret << 3) + (ret << 1) + (c ^ 48);
  }
  return pos ? ret : -ret;
}
const size_t N = 1e5 + 5;
const size_t M = 3e5 + 5;
const size_t V = N << 5;
const int INF = 1e9;
int rt, seg[V], lc[V], rc[V], tot;
void clean() {
  rt = tot = 0;
  memset(lc, 0, sizeof lc);
  memset(rc, 0, sizeof rc);
  fill(begin(seg), end(seg), -INF);
}
void pushup(int x) { seg[x] = max(seg[lc[x]], seg[rc[x]]); }
void push(int &x, int tl, int tr, int p, int val) {
  if (!x) x = ++tot;
  if (tl + 1 == tr) {
    if (val > seg[x]) {
      seg[x] = val;
    }
    return;
  }
  int mid = (tl + tr) >> 1;
  if (p < mid) {
    push(lc[x], tl, mid, p, val);
  } else {
    push(rc[x], mid, tr, p, val);
  }
  pushup(x);
}
int query(int x, int tl, int tr, int l, int r) {
  if (tl >= r || tr <= l || !x) return -INF;
  if (l <= tl && tr <= r) {
    return seg[x];
  }
  int mid = (tl + tr) >> 1;
  return max(query(lc[x], tl, mid, l, r), query(rc[x], mid, tr, l, r));
}
int n, arr[N], ans[M];
vector<pair<int, int> > que[N], upd[N];
int main() {
  n = read();
  generate_n(arr, n, read);
  int m = read();
  for (int i = 0; i < m; ++i) {
    int l = read() - 1, r = read();
    que[l].emplace_back(r, i);
  }
  int N = *max_element(arr, arr + n) + 1;
  clean();
  for (int i = 0; i < n; ++i) {
    {
      int lb = 0;
      while (lb <= arr[i]) {
        int id = query(rt, 0, N, lb, arr[i] + 1);
        if (id < 0) break;
        upd[id].emplace_back(arr[i] - arr[id], i);
        lb = (arr[i] + arr[id]) / 2 + 1;
      }
    }
    {
      int rb = N - 1;
      while (arr[i] <= rb) {
        int id = query(rt, 0, N, arr[i], rb + 1);
        if (id < 0) break;
        upd[id].emplace_back(arr[id] - arr[i], i);
        rb = (arr[i] + arr[id] - 1) / 2;
      }
    }
    push(rt, 0, N, arr[i], i);
  }
  clean();
  for (int i = n; i--;) {
    for (auto [val, pos] : upd[i]) {
      push(rt, 0, n, pos, -val);
    }
    for (auto [r, id] : que[i]) {
      ans[id] = -query(rt, 0, n, i, r);
    }
  }
  for (int i = 0; i < m; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
