#include <bits/stdc++.h>
using namespace std;
int IN() {
  int x = 0, f = 0, ch;
  for (; (ch = getchar()) < '0' || ch > '9';) f = (ch == '-');
  for (; ch >= '0' && ch <= '9'; (ch = getchar())) x = x * 10 + ch - '0';
  return f ? -x : x;
}
int N, Q, A[300005], T[300005], Ans[300005];
int C, Rt[300005], ls[4000005], rs[4000005], Max[4000005];
vector<pair<int, int> > G[300005];
struct Opt {
  int l, r, ID;
  bool operator<(const Opt& b) const { return r < b.r; }
} O[300005];
void Add(int x, int v) {
  x = N - x + 1;
  for (; x <= N; x += x & -x) T[x] = min(T[x], v);
}
int Ask(int x) {
  int ret = (1 << 30);
  x = N - x + 1;
  for (; x; x -= x & -x) ret = min(ret, T[x]);
  return ret;
}
void Modify(int& u, int l, int r, int x, int k) {
  int v = u;
  u = ++C;
  ls[u] = ls[v];
  rs[u] = rs[v];
  Max[u] = max(Max[v], k);
  if (l == r) return;
  int Mid = (l + r) >> 1;
  if (x <= Mid)
    Modify(ls[u], l, Mid, x, k);
  else
    Modify(rs[u], Mid + 1, r, x, k);
}
int Query(int u, int l, int r, int x, int y) {
  if (!u || (x <= l && r <= y)) return Max[u];
  int Mid = (l + r) >> 1;
  if (y <= Mid) return Query(ls[u], l, Mid, x, y);
  if (x > Mid) return Query(rs[u], Mid + 1, r, x, y);
  return max(Query(ls[u], l, Mid, x, y), Query(rs[u], Mid + 1, r, x, y));
}
int main(int argc, char* argv[]) {
  N = IN();
  for (int i = 1, lim = N; i <= lim; i++) A[i] = IN(), T[i] = (1 << 30);
  for (int i = 1, lim = N; i <= lim; i++) {
    Rt[i] = Rt[i - 1];
    Modify(Rt[i], 0, (1 << 30), A[i], i);
    {
      int j = Query(Rt[i - 1], 0, (1 << 30), 0, A[i]);
      for (; j;) {
        int v = A[i] - A[j];
        G[i].push_back(make_pair(j, v));
        if (!v) break;
        j = Query(Rt[j - 1], 0, (1 << 30), A[i] - v / 2, A[i]);
      }
    }
    {
      int j = Query(Rt[i - 1], 0, (1 << 30), A[i], (1 << 30));
      for (; j;) {
        int v = A[j] - A[i];
        G[i].push_back(make_pair(j, v));
        if (!v) break;
        j = Query(Rt[j - 1], 0, (1 << 30), A[i], A[i] + v / 2);
      }
    }
  }
  Q = IN();
  for (int i = 1, lim = Q; i <= lim; i++) O[i] = (Opt){IN(), IN(), i};
  sort(O + 1, O + Q + 1);
  for (int i = 1, j = 1; i <= N; i++) {
    for (int k = 1, lim = G[i].size(); k <= lim; k++)
      Add(G[i][k - 1].first, G[i][k - 1].second);
    for (; j <= Q && O[j].r == i; j++) Ans[O[j].ID] = Ask(O[j].l);
  }
  for (int i = 1, lim = Q; i <= lim; i++) printf("%d\n", Ans[i]);
  return 0;
}
