#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m, a[N], l, r, c[N], ans[N], inf = 1e9, tot, mx[N << 5], lc[N << 5],
                                    rc[N << 5], rt;
vector<pair<int, int> > q[N];
void add(int x, int y) {
  for (int i = x; i; i -= i & (-i)) c[i] = min(c[i], y);
}
int ask(int x) {
  int ans = inf;
  for (int i = x; i <= n; i += i & (-i)) ans = min(ans, c[i]);
  return ans;
}
void modify(int &p, int l, int r, int pos, int v) {
  if (!p) p = ++tot;
  if (l == r) {
    mx[p] = max(mx[p], v);
    return;
  }
  int mid = (l + r) / 2;
  if (pos <= mid)
    modify(lc[p], l, mid, pos, v);
  else
    modify(rc[p], mid + 1, r, pos, v);
  mx[p] = max(mx[lc[p]], mx[rc[p]]);
}
int query(int p, int l, int r, int lx, int rx) {
  if (!p) return 0;
  if (l >= lx && r <= rx) return mx[p];
  int mid = (l + r) / 2, ans = 0;
  if (lx <= mid) ans = max(ans, query(lc[p], l, mid, lx, rx));
  if (rx > mid) ans = max(ans, query(rc[p], mid + 1, r, lx, rx));
  return ans;
}
void solve() {
  for (int i = 1; i <= n; i++) c[i] = inf;
  for (int i = 1; i <= tot; i++) lc[i] = rc[i] = mx[i] = 0;
  tot = rt = 0;
  for (int i = 1; i <= n; i++) {
    int j = query(rt, 0, inf, a[i], inf);
    while (j) {
      add(j, a[j] - a[i]);
      j = query(rt, 0, inf, a[i], (a[i] + a[j]) / 2 - ((a[i] + a[j]) % 2 == 0));
    }
    modify(rt, 0, inf, a[i], i);
    for (auto v : q[i]) ans[v.second] = min(ans[v.second], ask(v.first));
  }
}
signed main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &l, &r), ans[i] = inf;
    q[r].push_back(make_pair(l, i));
  }
  solve();
  for (int i = 1; i <= n; i++) a[i] = inf - a[i];
  solve();
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
