#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 3e5;
const int TN = 33 * N;
const int W = 1e9;
const int inf = 0x3f3f3f3f;
namespace IO {
inline int read() {
  int s = 0, ww = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') ww = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    s = 10 * s + ch - '0';
    ch = getchar();
  }
  return s * ww;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar('0' + x % 10);
}
}  // namespace IO
using namespace IO;
struct ValueSegTree {
  int cnt;
  int lc[TN + 5], rc[TN + 5], maxn[TN + 5];
  inline void init() { cnt = 1; }
  inline void pushup(int u) { maxn[u] = max(maxn[lc[u]], maxn[rc[u]]); }
  int query(int u, int l, int r, int ql, int qr) {
    if (!u) return 0;
    if (ql == l && qr == r) return maxn[u];
    int m = (l + r) >> 1;
    if (qr <= m)
      return query(lc[u], l, m, ql, qr);
    else if (ql > m)
      return query(rc[u], m + 1, r, ql, qr);
    else
      return max(query(lc[u], l, m, ql, m), query(rc[u], m + 1, r, m + 1, qr));
  }
  void ud(int u, int l, int r, int ax, int x) {
    if (l == r) {
      maxn[u] = max(maxn[u], x);
      return;
    }
    int m = (l + r) >> 1;
    if (ax <= m) {
      if (!lc[u]) lc[u] = ++cnt;
      ud(lc[u], l, m, ax, x);
    } else {
      if (!rc[u]) rc[u] = ++cnt;
      ud(rc[u], m + 1, r, ax, x);
    }
    pushup(u);
  }
} VT;
struct SegTree {
  int minn[(N << 2) + 5];
  inline void init(int u, int l, int r) {
    minn[u] = inf;
    if (l == r) return;
    int m = (l + r) >> 1;
    init((u << 1), l, m);
    init(((u << 1) | 1), m + 1, r);
  }
  inline void pushup(int u) {
    minn[u] = min(minn[(u << 1)], minn[((u << 1) | 1)]);
  }
  void ud(int u, int l, int r, int x, int cur) {
    if (l == r) {
      minn[u] = min(minn[u], cur);
      return;
    }
    int m = (l + r) >> 1;
    if (x <= m)
      ud((u << 1), l, m, x, cur);
    else
      ud(((u << 1) | 1), m + 1, r, x, cur);
    pushup(u);
  }
  int query(int u, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) return minn[u];
    int m = (l + r) >> 1;
    if (qr <= m)
      return query((u << 1), l, m, ql, qr);
    else if (ql > m)
      return query(((u << 1) | 1), m + 1, r, ql, qr);
    else
      return min(query((u << 1), l, m, ql, m),
                 query(((u << 1) | 1), m + 1, r, m + 1, qr));
  }
} T;
int a[N + 5], ans[M + 5];
int n, m;
vector<pair<int, int> > q[N + 5];
int main() {
  n = read();
  for (register int i = 1; i <= n; i++) a[i] = read();
  m = read();
  for (register int i = 1; i <= m; i++) {
    int l = read(), r = read();
    q[r].push_back(make_pair(l, i));
  }
  VT.init();
  T.init(1, 1, n);
  for (register int r = 1; r <= n; r++) {
    int L, R = a[r], i;
    i = VT.query(1, 0, W, 0, R);
    if (i) {
      T.ud(1, 1, n, i, R - a[i]);
      L = a[i];
      while (L < R) {
        i = VT.query(1, 0, W, (L + 1 + R) >> 1, R);
        if (!i) break;
        T.ud(1, 1, n, i, R - a[i]);
        L = a[i];
      }
    }
    L = a[r];
    i = VT.query(1, 0, W, L, W);
    if (i) {
      T.ud(1, 1, n, i, a[i] - L);
      R = a[i];
      while (L < R) {
        i = VT.query(1, 0, W, L, (L + R - 1) >> 1);
        if (!i) break;
        T.ud(1, 1, n, i, a[i] - L);
        R = a[i];
      }
    }
    VT.ud(1, 0, W, a[r], r);
    for (i = 0; i < q[r].size(); i++) {
      int l = q[r][i].first, id = q[r][i].second;
      ans[id] = T.query(1, 1, n, l, r - 1);
    }
  }
  for (register int i = 1; i <= m; i++) write(ans[i]), putchar('\n');
  return 0;
}
