#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = 300005, inf = 0x7f7f7f7f;
struct node {
  int id, l, r;
} q[M];
bool operator<(node a, node b) { return a.r < b.r; }
int val[N << 3], a[N], ans[M], Min;
vector<int> v[N << 3];
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 1) + (x << 3) + ch - '0';
  return x * f;
}
void build(int rt, int l, int r) {
  val[rt] = inf;
  if (l == r) {
    v[rt].push_back(a[l]);
    return;
  }
  int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1;
  build(ls, l, mid);
  build(rs, mid + 1, r);
  v[rt].resize(r - l + 1);
  merge(v[ls].begin(), v[ls].end(), v[rs].begin(), v[rs].end(), v[rt].begin());
}
void modify(int rt, int l, int r, int R, int x) {
  if (R == r) {
    auto it = lower_bound(v[rt].begin(), v[rt].end(), x);
    if (it < v[rt].end()) val[rt] = min(val[rt], abs(x - *it));
    if (--it >= v[rt].begin()) val[rt] = min(val[rt], abs(x - *it));
    if (val[rt] >= Min) return;
    if (l == r) {
      Min = val[rt];
      return;
    }
  }
  int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1;
  if (R > mid) modify(rs, mid + 1, r, R, x);
  modify(ls, l, mid, min(mid, R), x);
  val[rt] = min(val[ls], val[rs]);
  Min = min(Min, val[rt]);
}
int query(int rt, int l, int r, int L, int R) {
  if (l == L && r == R) return val[rt];
  int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1, res = inf;
  if (L <= mid) res = min(res, query(ls, l, mid, L, min(mid, R)));
  if (R > mid) res = min(res, query(rs, mid + 1, r, max(L, mid + 1), R));
  return res;
}
int main() {
  int n = read();
  for (register int i = (1); i <= (n); ++i) a[i] = read();
  int m = read();
  for (register int i = (1); i <= (m); ++i) {
    int l = read(), r = read();
    q[i] = (node){i, l, r};
  }
  sort(q + 1, q + m + 1);
  build(1, 1, n);
  for (int i = 2, j = 1; i <= n; i++) {
    Min = inf;
    modify(1, 1, n, i - 1, a[i]);
    for (; j <= m && q[j].r == i; j++)
      ans[q[j].id] = query(1, 1, n, q[j].l, q[j].r - 1);
  }
  for (register int i = (1); i <= (m); ++i) printf("%d\n", ans[i]);
  return 0;
}
