#include <bits/stdc++.h>
using namespace std;
const long long oo = 0x3f3f3f3f3f3f3f3fll;
const int LGN = 25;
const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
int n, a[N], m, l[N], r[N];
int mem[N * LGN], cnt;
int* alloc(int x) {
  int* p = mem + cnt;
  cnt += x;
  return p;
}
struct {
  int* a;
  int ans;
} st[4 * N];
void build(int p = 1, int L = 1, int R = n) {
  if (R < L) return;
  if (L == R) {
    st[p].a = alloc(1);
    st[p].a[0] = ::a[L];
    st[p].ans = oo;
    return;
  }
  int m = (L + R) >> 1;
  build(2 * p, L, m), build(2 * p + 1, m + 1, R);
  st[p].a = alloc(R - L + 1);
  int* lf = st[2 * p].a;
  int* ri = st[2 * p + 1].a;
  merge(lf, lf + (m - L + 1), ri, ri + (R - m), st[p].a);
  st[p].ans = oo;
  for (long long i = 1, __R = R - L; i <= __R; i++)
    st[p].ans = min(st[p].ans, st[p].a[i] - st[p].a[i - 1]);
}
int query(int l, int r, int p = 1, int L = 1, int R = n);
void update(int i, int v, int& d, int p = 1, int L = 1, int R = n) {
  if (R < L || i < L || R < i) return;
  if (L == R) {
    st[p].ans = min(st[p].ans, abs(st[p].a[0] - v));
    d = min(d, st[p].ans);
    return;
  }
  int j = lower_bound(st[p].a, st[p].a + (R - L + 1), v) - st[p].a;
  if ((j == 0 || d <= v - st[p].a[j - 1]) &&
      (j == R - L + 1 || d <= st[p].a[j] - v)) {
    d = min(d, query(L, R, p, L, R));
    return;
  }
  int m = (L + R) >> 1;
  if (i <= m)
    update(i, v, d, 2 * p, L, m);
  else {
    update(i, v, d, 2 * p + 1, m + 1, R);
    update(m, v, d, 2 * p, L, m);
  }
  st[p].ans = min(st[p].ans, min(st[2 * p].ans, st[2 * p + 1].ans));
}
int query(int l, int r, int p, int L, int R) {
  if (R < L || r < L || R < l) return oo;
  if (l <= L && R <= r) return st[p].ans;
  int m = (L + R) >> 1;
  return min(query(l, r, 2 * p, L, m), query(l, r, 2 * p + 1, m + 1, R));
}
int main() {
  std::ios::sync_with_stdio(false);
  scanf("%d", &(n));
  for (long long i = 1, __R = n; i <= __R; i++) scanf("%d", &(a[i]));
  build();
  scanf("%d", &(m));
  static int idx[N];
  for (long long i = 1, __R = m; i <= __R; i++)
    scanf("%d%d", &(l[i]), &(r[i])), idx[i] = i;
  sort(idx + 1, idx + m + 1, [](int i, int j) { return r[i] < r[j]; });
  int curr = 1;
  static int ans[N];
  for (long long j = 1, __R = m; j <= __R; j++) {
    int i = idx[j];
    while (curr < r[i]) {
      curr++;
      int d = oo;
      update(curr - 1, a[curr], d);
    }
    ans[i] = query(l[i], r[i]);
  }
  for (long long i = 1, __R = m; i <= __R; i++) printf("%d\n", ans[i]);
  return 0;
}
