#include <bits/stdc++.h>
using namespace std;
int const maxn = 100003, inf = 0x3f3f3f3f;
inline int read() {
  int x = 0, c = getchar();
  while (c < '0' && c < '9') c = getchar();
  while ('0' <= c && c <= '9') x = 10 * x + c - '0', c = getchar();
  return x;
}
struct Query {
  int id, l, r;
};
inline bool operator<(Query const &lhs, Query const &rhs) {
  return lhs.r < rhs.r;
}
int n = 0, m = 0;
int a[maxn];
Query q[maxn * 3];
int Ans[maxn * 3];
vector<int> seg[maxn << 2];
int ans[maxn << 2];
void build(int p, int L, int R) {
  seg[p].insert(seg[p].end(), a + L, a + R + 1);
  sort(seg[p].begin(), seg[p].end());
  ans[p] = inf;
  if (L == R) return;
  int mid = (L + R) >> 1;
  build(p << 1, L, mid);
  build(p << 1 | 1, mid + 1, R);
}
void modify(int p, int L, int R, int pos, int x) {
  static int miRight = inf;
  if (L == 1 && R == n) miRight = inf;
  if (R <= pos) {
    auto it = upper_bound(seg[p].begin(), seg[p].end(), x);
    if (it != seg[p].end()) ans[p] = min(ans[p], *it - x);
    if (it != seg[p].begin()) ans[p] = min(ans[p], x - *(it - 1));
    if (ans[p] >= miRight) return;
    if (L == R) {
      miRight = min(miRight, ans[p]);
      return;
    }
  }
  int mid = (L + R) >> 1;
  if (pos > mid) modify(p << 1 | 1, mid + 1, R, pos, x);
  modify(p << 1, L, mid, pos, x);
  ans[p] = min(ans[p << 1], ans[p << 1 | 1]);
  miRight = min(miRight, ans[p]);
}
int query(int p, int L, int R, int l, int r) {
  if (l <= L && R <= r) return ans[p];
  int mid = (L + R) >> 1;
  if (r <= mid)
    return query(p << 1, L, mid, l, r);
  else if (l > mid)
    return query(p << 1 | 1, mid + 1, R, l, r);
  else
    return min(query(p << 1 | 1, mid + 1, R, l, r),
               query(p << 1, L, mid, l, r));
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    q[i].l = read();
    q[i].r = read();
    q[i].id = i;
    Ans[i] = inf;
  }
  sort(q + 1, q + m + 1);
  build(1, 1, n);
  for (int i = 2, j = 1; i <= n && j <= m; ++i) {
    modify(1, 1, n, i - 1, a[i]);
    while (j <= m && q[j].r == i) {
      Ans[q[j].id] = query(1, 1, n, q[j].l, i);
      ++j;
    }
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", Ans[i]);
  return 0;
}
