#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
struct node {
  int l, r, id;
  bool operator<(const node &a) const {
    if (a.l == l && a.r == r) {
      return id < a.id;
    }
    if (a.l == l) return r < a.r;
    return l < a.l;
  }
} query[maxn];
struct Node {
  set<int> T;
  int mi;
} T[maxn];
int n, m, b[maxn], ans[maxn];
void build(int x, int l, int r) {
  T[x].mi = (1 << 30);
  for (int i = l; i <= r; i++) T[x].T.insert(b[i]);
  if (l == r) return;
  int mid = (l + r) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}
int Query(int x, int l, int r, int L, int R) {
  if (l > R || L > r) return (1 << 30);
  if (L <= l && r <= R) return T[x].mi;
  int mid = (l + r) / 2;
  return min(Query(x << 1, l, mid, L, R), Query(x << 1 | 1, mid + 1, r, L, R));
}
void upd(int x, int l, int r, int L, int R, int val, int &mi) {
  if (l > R || L > r) return;
  if (l == r) {
    T[x].mi = min(T[x].mi, abs(val - b[l]));
    mi = min(mi, T[x].mi);
    return;
  }
  set<int> &t = T[x].T;
  auto p = t.lower_bound(val);
  if ((p == t.end() || (*p - val) >= mi) &&
      (p == t.begin() || (val - *(--p)) >= mi)) {
    mi = min(mi, Query(x, l, r, L, R));
    return;
  }
  int mid = (l + r) / 2;
  upd(x << 1, l, mid, L, R, val, mi);
  upd(x << 1 | 1, mid + 1, r, L, R, val, mi);
  T[x].mi = min(T[x << 1].mi, T[x << 1 | 1].mi);
}
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &b[i]);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++)
    scanf("%d%d", &query[i].l, &query[i].r), query[i].id = i;
}
int main() {
  init();
  sort(query + 1, query + 1 + m);
  build(1, 1, n);
  for (int i = m, l = n; i; i--) {
    for (; l >= query[i].l; l--) {
      int inf = (1 << 30);
      upd(1, 1, n, l + 1, n, b[l], inf);
    }
    ans[query[i].id] = Query(1, 1, n, query[i].l, query[i].r);
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << endl;
  return 0;
}
