#include <bits/stdc++.h>
using namespace std;
const double PI = acos(0) * 2;
const double EPS = 1e-8;
const long long MOD = 1e9 + 7;
const int MAXN = 3e5 + 5;
const int oo = 2e9 + 5;
const double foo = 1e30;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcounll(s);
}
template <class T>
T sqr(T x) {
  return x * x;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
int val[MAXN << 4], _lz[MAXN << 4], val1[MAXN << 4], _lz1[MAXN << 4];
int n, totVal, a[MAXN], m, l[MAXN], r[MAXN];
map<int, int> mm;
int pos[MAXN], ans[MAXN];
vector<pair<int, int> > q[MAXN];
void build(int node, int L, int R) {
  val[node] = oo;
  _lz[node] = -1;
  if (L < R) {
    int mid = (L + R) >> 1;
    build(node * 2, L, mid);
    build(node * 2 + 1, mid + 1, R);
  }
}
void pushdown(int node) {
  if (~_lz[node]) {
    val[node * 2] = min(val[node * 2], _lz[node]);
    val[node * 2 + 1] = min(val[node * 2 + 1], _lz[node]);
    if (~_lz[node * 2])
      _lz[node * 2] = min(_lz[node * 2], _lz[node]);
    else
      _lz[node * 2] = _lz[node];
    if (~_lz[node * 2 + 1])
      _lz[node * 2 + 1] = min(_lz[node * 2 + 1], _lz[node]);
    else
      _lz[node * 2 + 1] = _lz[node];
  }
  _lz[node] = -1;
}
void update(int node, int L, int R, int l, int r, int v) {
  if (l > R || r < L) return;
  if (l <= L && R <= r) {
    if (val[node] > v) {
      val[node] = v;
    }
    if (~_lz[node])
      _lz[node] = min(_lz[node], v);
    else
      _lz[node] = v;
    return;
  }
  if (L < R) {
    pushdown(node);
    int mid = (L + R) >> 1;
    update(node * 2, L, mid, l, r, v);
    update(node * 2 + 1, mid + 1, R, l, r, v);
    val[node] = min(val[node * 2], val[node * 2 + 1]);
  }
}
int query(int node, int L, int R, int pos) {
  if (pos < L || pos > R) return oo;
  if (L == pos && R == L) return val[node];
  if (L < R) {
    pushdown(node);
    int mid = (L + R) >> 1;
    return min(query(node * 2, L, mid, pos),
               query(node * 2 + 1, mid + 1, R, pos));
  }
}
void build1(int node, int L, int R) {
  val1[node] = -1;
  _lz1[node] = -1;
  if (L < R) {
    int mid = (L + R) >> 1;
    build1(node * 2, L, mid);
    build1(node * 2 + 1, mid + 1, R);
  }
}
void pushdown1(int node) {
  if (~_lz1[node]) {
    val1[node * 2] = max(_lz1[node], val1[node * 2]);
    val1[node * 2 + 1] = max(_lz1[node], val1[node * 2 + 1]);
    _lz1[node * 2] = max(_lz1[node], _lz1[node * 2]);
    _lz1[node * 2 + 1] = max(_lz1[node], _lz1[node * 2 + 1]);
  }
  _lz1[node] = -1;
}
void update1(int node, int L, int R, int pos, int v) {
  if (pos > R || pos < L) return;
  if (pos <= L && R <= pos) {
    if (v > val1[node]) {
      val1[node] = v;
    }
    _lz1[node] = max(_lz1[node], v);
    return;
  }
  if (L < R) {
    pushdown1(node);
    int mid = (L + R) >> 1;
    if (val1[node] < v) update1(node * 2, L, mid, pos, v);
    if (val1[node] < v) update1(node * 2 + 1, mid + 1, R, pos, v);
    val1[node] = max(val1[node * 2], val1[node * 2 + 1]);
  }
}
int query1(int node, int L, int R, int l, int r) {
  if (l > R || r < L) return -1;
  if (l <= L && R <= r) return val1[node];
  if (L < R) {
    pushdown(node);
    int mid = (L + R) >> 1;
    return max(query1(node * 2, L, mid, l, r),
               query1(node * 2 + 1, mid + 1, R, l, r));
  }
}
void solve() {
  build(1, 0, n - 1);
  build1(1, 0, totVal - 1);
  for (int i = 0; i < n; i++) {
    int curY = oo;
    while (true) {
      int lo = mm[a[i]], hi = totVal - 1, findY = -1;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (pos[mid] - a[i] < curY - pos[mid]) {
          findY = mid;
          lo = mid + 1;
        } else
          hi = mid - 1;
      }
      if (!~findY) break;
      int now = query1(1, 0, totVal - 1, mm[a[i]], findY);
      if (!~now) break;
      lo = mm[a[i]], hi = findY;
      curY = a[now];
      update(1, 0, n - 1, 0, now, curY - a[i]);
    }
    for (int j = 0; j < ((int)(q[i]).size()); j++) {
      ans[q[i][j].second] =
          min(ans[q[i][j].second], query(1, 0, n - 1, q[i][j].first));
    }
    update1(1, 0, totVal - 1, mm[a[i]], i);
  }
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    mm[a[i]];
  }
  totVal = 0;
  for (map<int, int>::iterator it = mm.begin(); it != mm.end(); it++) {
    pos[totVal] = it->first;
    it->second = totVal++;
  }
  cin >> m;
  for (int i = 0; i < m; i++) ans[i] = oo;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &l[i], &r[i]);
    r[i]--;
    l[i]--;
    q[r[i]].push_back(make_pair(l[i], i));
  }
  solve();
  int j = n - 1;
  for (int i = 0; i < n / 2; i++) {
    swap(a[i], a[j]);
    j--;
  }
  for (int i = 0; i < n; i++) q[i].clear();
  for (int i = 0; i < m; i++) {
    l[i] = n - 1 - l[i];
    r[i] = n - 1 - r[i];
    q[l[i]].push_back(make_pair(r[i], i));
  }
  solve();
  for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  return 0;
}
