#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
const int N = 101000;
const int M = 301000;
const int K = 300;
const int Inf = 2000000000;
pair<int, int> a[N];
int n, x[M], u[N];
struct L {
  int l, r, x;
  L(int l = 0, int r = 0, int x = 0) : l(l), r(r), x(x) {}
};
bool cmpr(const L &a, const L &b) { return a.r < b.r; }
struct LS {
  L e[N], f[N];
  void rem(int i) {
    int j = u[i];
    f[i] = e[j];
    int l = e[j].l;
    int r = e[j].r;
    if (l >= 0) e[l].r = r;
    if (r < n) e[r].l = l;
  }
  void add(int i, int &v) {
    int j = u[i];
    e[j] = f[i];
    if (e[j].l >= 0) {
      v = min(v, e[j].x - e[e[j].l].x);
      e[e[j].l].r = j;
    }
    if (e[j].r < n) {
      v = min(v, e[e[j].r].x - e[j].x);
      e[e[j].r].l = j;
    }
  }
};
LS e, s;
vector<L> q[N / K + 1];
void proc(vector<L> &q, int l) {
  if (q.empty()) return;
  int i, r;
  sort(q.begin(), q.end(), cmpr);
  s = e;
  for (i = l; i < l + K; s.rem(i), i++)
    ;
  for (i = n - 1; i >= l + K; s.rem(i), i--)
    ;
  for (i = n - 1; i >= l + K; e.rem(i), i--)
    ;
  r = l + K;
  int v = Inf;
  for (auto &t : q) {
    int vv = v;
    for (; r <= t.r; s.add(r, v), e.add(r, vv), r++)
      ;
    for (i = l + K - 1; i > t.r; e.rem(i), i--)
      ;
    for (i = l; i < l + K && i <= t.r; e.rem(i), i++)
      ;
    vv = v;
    for (i = min(l + K - 1, t.r); i >= t.l; e.add(i, vv), i--)
      ;
    x[t.x] = vv;
    for (; i >= l; e.add(i, vv), i--)
      ;
    for (i = t.r + 1; i < l + K; e.add(i, vv), i++)
      ;
  }
  for (; r < n; e.add(r, v), r++)
    ;
}
int main() {
  int i, j, k, t;
  scanf("%d", &n);
  for (i = 0; i < n; scanf("%d", &a[i].first), a[i].second = i, i++)
    ;
  for (; n % K; a[n] = {0, n}, n++)
    ;
  sort(a, a + n);
  for (i = 0; i < n;
       u[a[i].second] = i, e.e[i] = L(i - 1, i + 1, a[i].first), i++)
    ;
  scanf("%d", &k);
  for (t = 0; t < k;
       scanf("%d%d", &i, &j), i--, j--, q[i / K].push_back(L(i, j, t)), t++)
    ;
  for (t = 0; t < n / K; t++) {
    j = t * K;
    proc(q[t], j);
    for (i = j; i < j + K; e.rem(i), i++)
      ;
  }
  for (i = 0; i < k; printf("%d\n", x[i]), i++)
    ;
  return 0;
}
