#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 3e2, M = 3e5 + 3e2, inf = 2e9 + 10;
int fmin(int x, int y) { return (((x - y) >> 31) & (x ^ y)) ^ y; }
int ANS[M], NEW[N], A[N], UNQ[N], DF[N], DS[N], n, q, sz, l, r, a;
vector<int> FIXR[N], FIXRID[N];
void addf(int ind, int d) {
  for (ind = (n - ind + 1); ind <= n; ind += (ind & -ind))
    DF[ind] = fmin(DF[ind], d);
}
int getf(int ind) {
  int sm = inf;
  for (ind = (n - ind + 1); ind; ind -= (ind & -ind)) sm = fmin(DF[ind], sm);
  return sm;
}
void adds(int ind, int d, int id = 1, int l = 1, int r = sz) {
  DS[id] = d;
  if (r == l) return;
  int mid = ((l + r) >> 1);
  if (ind <= mid)
    adds(ind, d, (id << 1), l, mid);
  else
    adds(ind, d, (id << 1 | 1), mid + 1, r);
}
int gets(int s, int e, int id = 1, int l = 1, int r = sz) {
  if (UNQ[l] >= s && UNQ[r] <= e) return (DS[id]);
  if (l == r) return (0);
  int mid = ((l + r) >> 1);
  int rt = 0;
  if (s <= UNQ[mid]) rt = max(rt, gets(s, e, (id << 1), l, mid));
  if (UNQ[mid + 1] <= e) rt = max(rt, gets(s, e, (id << 1 | 1), mid + 1, r));
  return (rt);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]), UNQ[i] = A[i];
  sort(UNQ + 1, UNQ + n + 1);
  sz = unique(UNQ + 1, UNQ + n + 1) - UNQ - 1;
  for (int i = 1; i <= n; i++)
    NEW[i] = lower_bound(UNQ + 1, UNQ + sz + 1, A[i]) - UNQ;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%d %d", &l, &r), FIXR[r].push_back(l), FIXRID[r].push_back(i);
  memset(DF, 63, sizeof(DF));
  for (int i = 2; i <= n; i++) {
    adds(NEW[i - 1], i - 1);
    l = -inf, r = inf, a = i - 1;
    while (l <= r) {
      a = gets(l, r);
      if (!a) break;
      addf(a, abs(A[a] - A[i]));
      if (A[a] >= A[i]) r = (A[i] + A[a] - 1) >> 1;
      if (A[a] <= A[i]) l = (A[i] + A[a] + 2) >> 1;
    }
    for (int j = 0; j < (int)FIXR[i].size(); j++)
      ANS[FIXRID[i][j]] = getf(FIXR[i][j]);
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ANS[i]);
}
