#include <bits/stdc++.h>
using namespace std;
const int N = 5E5;
set<int> num[N];
vector<pair<int, int> > vec[N];
int n, m, s[N], ans[N], val[N], now;
void edit(int t, int l, int r, int p, int v) {
  if (l > p) return;
  if (l == r) {
    if (p != l) now = min(now, val[t] = min(val[t], abs(v - s[l])));
    return;
  }
  int d = l + r >> 1, g = min(abs(v - *num[t].lower_bound(v)),
                              abs(v - *--num[t].lower_bound(v)));
  if (g < now)
    edit(t << 1 | 1, d + 1, r, p, v), edit(t << 1, l, d, p, v),
        val[t] = min(val[t << 1], val[t << 1 | 1]);
  now = min(now, val[t]);
}
void ins(int t, int l, int r, int p, int v) {
  if (l == r) return;
  int d = l + r >> 1;
  num[t].insert(v);
  if (p <= d)
    ins(t << 1, l, d, p, v);
  else
    ins(t << 1 | 1, d + 1, r, p, v);
}
int qry(int t, int l, int r, int p) {
  if (l >= p) return val[t];
  if (r < p) return 2E9;
  int d = l + r >> 1;
  return min(qry(t << 1 | 1, d + 1, r, p), qry(t << 1, l, d, p));
}
signed main() {
  for (int i = 0; i < N; ++i)
    val[i] = 2E9, num[i].insert(-2E9), num[i].insert(2E9);
  cin >> n;
  for (int i = 1; i <= n; ++i) scanf("%d", s + i);
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    vec[r].push_back(make_pair(l, i));
  }
  for (int i = 1; i <= n; ++i) {
    now = 2E9, edit(1, 1, n, i, s[i]), ins(1, 1, n, i, s[i]);
    for (auto p : vec[i]) ans[p.second] = qry(1, 1, n, p.first);
  }
  for (int i = 1; i <= m; ++i) cout << ans[i] << endl;
}
