#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int sum = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  if (f) return -sum;
  return sum;
}
const int N = 300005;
const int orz = 2000000000;
int n, m, a[N], ans[N], t[N * 4];
set<int> S[N * 4];
inline void build(int p, int l, int r) {
  t[p] = orz;
  for (int i = l; i <= r; i++) S[p].insert(a[i]);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
}
int OP, v;
set<int>::iterator it;
inline int ask(int p, int l, int r, int L, int R) {
  if (l == L && r == R) return t[p];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return ask(p << 1, l, mid, L, R);
  else if (L > mid)
    return ask(p << 1 | 1, mid + 1, r, L, R);
  else
    return min(ask(p << 1, l, mid, L, mid),
               ask(p << 1 | 1, mid + 1, r, mid + 1, R));
}
inline void up(int p, int l, int r, int L, int R) {
  if (l == r) {
    t[p] = min(t[p], abs(v - a[l])), OP = min(OP, t[p]);
    return;
  }
  it = S[p].lower_bound(v);
  if (it == S[p].end() || (*(it)-v) >= OP)
    if (it == S[p].begin() || (v - *(--it)) >= OP) {
      OP = min(OP, ask(p, l, r, L, R));
      return;
    }
  int mid = (l + r) >> 1;
  if (R <= mid)
    up(p << 1, l, mid, L, R);
  else if (L > mid)
    up(p << 1 | 1, mid + 1, r, L, R);
  else
    up(p << 1 | 1, mid + 1, r, mid + 1, R), up(p << 1, l, mid, L, mid);
  t[p] = min(t[p << 1], t[p << 1 | 1]);
}
struct ex {
  int l, r, id;
} q[N];
inline bool operator<(const ex &a, const ex &b) { return a.r < b.r; }
int main() {
  int i, j;
  n = read();
  for (i = 1; i <= n; i++) a[i] = read();
  build(1, 1, n);
  m = read();
  for (i = 1; i <= m; i++) q[i].l = read(), q[i].r = read(), q[i].id = i;
  sort(q + 1, q + m + 1);
  for (j = 2, i = 1; i <= m; i++) {
    while (j <= q[i].r) OP = orz, v = a[j], up(1, 1, n, 1, j - 1), j++;
    ans[q[i].id] = ask(1, 1, n, q[i].l, q[i].r);
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
