#include <bits/stdc++.h>
using namespace std;
int N, M, SQ;
int pred[100005], succ[100005], dp[100005][655];
long long best, A[100005], mem[100005], ans[3 * 100005];
pair<int, int> B[100005];
vector<pair<pair<int, int>, int> > bucket[655];
void del(int x) {
  succ[pred[x]] = succ[x];
  pred[succ[x]] = pred[x];
}
void create(int s, int e) {
  int p = 0;
  succ[0] = N + 1;
  pred[N + 1] = 0;
  for (int i = 0; i < N; i++) {
    int c = B[i].second;
    if (c < s || c > e) continue;
    succ[p] = c;
    pred[c] = p;
    succ[c] = N + 1;
    pred[N + 1] = c;
    p = c;
  }
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%I64d", &A[i]);
    B[i - 1] = make_pair(A[i], i);
    dp[i][1] = 2000000010LL;
  }
  scanf("%d", &M);
  SQ = N / sqrt(N + M) + 1;
  for (int sz = 2; sz <= SQ; sz++)
    for (int i = 1; i <= N; i++) {
      if (i + sz - 1 > N)
        dp[i][sz] = dp[i][sz - 1];
      else
        dp[i][sz] = min(abs(A[i] - A[i + sz - 1]),
                        (long long)min(dp[i + 1][sz - 1], dp[i][sz - 1]));
    }
  for (int i = 0; i < M; i++) {
    int l, r;
    scanf("%d", &l);
    scanf("%d", &r);
    if ((r - l + 1) > SQ)
      bucket[l / SQ].push_back(make_pair(make_pair(r, l), i));
    else
      ans[i] = dp[l][r - l + 1];
  }
  sort(B, B + N);
  A[0] = -2000000010LL;
  A[N + 1] = 2000000010LL;
  int bn = N / SQ + 1;
  for (int n = 0; n < bn; n++) {
    int p = n * SQ, q = p + SQ, ls = N;
    create(q, N);
    for (int i = N; i >= q; i--) del(i);
    for (int i = q; i <= N; i++) {
      ({
        succ[pred[i]] = pred[succ[i]] = i;
        best = min(A[i] - A[pred[i]], A[succ[i]] - A[i]);
      });
      if (q == i)
        mem[i] = best;
      else
        mem[i] = min(mem[i - 1], best);
    }
    create(p, N);
    sort(bucket[n].begin(), bucket[n].end(),
         greater<pair<pair<int, int>, int> >());
    for (auto &x : bucket[n]) {
      int r = x.first.first, l = x.first.second, id = x.second;
      while (ls > r) del(ls--);
      ans[id] = mem[r];
      for (int i = p; i < q; i++) del(i);
      for (int i = q - 1; i >= l; i--) {
        ({
          succ[pred[i]] = pred[succ[i]] = i;
          best = min(A[i] - A[pred[i]], A[succ[i]] - A[i]);
        });
        ans[id] = min(ans[id], best);
      }
      for (int i = l - 1; i >= p; i--)
        ({
          succ[pred[i]] = pred[succ[i]] = i;
          best = min(A[i] - A[pred[i]], A[succ[i]] - A[i]);
        });
    }
  }
  for (int i = 0; i < M; i++) printf("%I64d\n", ans[i]);
  return 0;
}
