#include <bits/stdc++.h>
using namespace std;
const signed int inf = (signed)(~0u >> 1), Val = 1e9;
typedef class SegTreeNode {
 public:
  int val;
  SegTreeNode *l, *r;
  SegTreeNode() {}
  void pushUp() {
    if (l) val = l->val;
    if (r) val = max(val, r->val);
  }
} SegTreeNode;
SegTreeNode pool[2000000];
SegTreeNode* top = pool;
SegTreeNode* newnode() {
  top->l = top->r = NULL;
  return top++;
}
typedef class SegTree {
 public:
  SegTreeNode* rt;
  SegTree() : rt(NULL) {}
  void update(SegTreeNode*& p, int l, int r, int ql, int qr, int val) {
    if (!p) p = newnode(), p->val = inf;
    if (l == ql && r == qr) {
      p->val = min(p->val, val);
      return;
    }
    int mid = (l + r) >> 1;
    if (qr <= mid)
      update(p->l, l, mid, ql, qr, val);
    else if (ql > mid)
      update(p->r, mid + 1, r, ql, qr, val);
    else {
      update(p->l, l, mid, ql, mid, val);
      update(p->r, mid + 1, r, mid + 1, qr, val);
    }
  }
  int query(SegTreeNode* p, int l, int r, int idx) {
    if (!p) return inf;
    if (l == r) return p->val;
    int mid = (l + r) >> 1, a = p->val, b = 0;
    if (idx <= mid)
      b = query(p->l, l, mid, idx);
    else
      b = query(p->r, mid + 1, r, idx);
    return min(a, b);
  }
  void update(SegTreeNode*& p, int l, int r, int idx, int val) {
    if (!p) p = newnode(), p->val = -1;
    if (l == r) {
      p->val = val;
      return;
    }
    int mid = (l + r) >> 1;
    if (idx <= mid)
      update(p->l, l, mid, idx, val);
    else
      update(p->r, mid + 1, r, idx, val);
    p->pushUp();
  }
  int query(SegTreeNode* p, int l, int r, int ql, int qr) {
    if (!p) return -1;
    if (l == ql && r == qr) return p->val;
    int mid = (l + r) >> 1;
    if (qr <= mid) return query(p->l, l, mid, ql, qr);
    if (ql > mid) return query(p->r, mid + 1, r, ql, qr);
    int a = query(p->l, l, mid, ql, mid);
    int b = query(p->r, mid + 1, r, mid + 1, qr);
    return max(a, b);
  }
} SegTree;
typedef class Query {
 public:
  int l, r, id, res;
  bool operator<(Query b) const { return r < b.r; }
} Query;
int n, m;
int* ar;
SegTree st, stv;
Query* qs;
inline void init() {
  scanf("%d", &n);
  ar = new int[(n + 1)];
  for (int i = 1; i <= n; i++) scanf("%d", ar + i);
  scanf("%d", &m);
  qs = new Query[(m + 1)];
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &qs[i].l, &qs[i].r);
    qs[i].id = i, qs[i].res = inf;
  }
}
inline void solve() {
  sort(qs + 1, qs + m + 1);
  for (int s = 0, c = 0; s < 2; s++) {
    st.rt = stv.rt = NULL, top = pool, c = 1;
    for (int i = 1; i <= n; i++) {
      int rlim = Val, idx;
      while (ar[i] <= rlim &&
             (idx = stv.query(stv.rt, 0, Val, ar[i], rlim)) != -1) {
        st.update(st.rt, 1, n, 1, idx, ar[idx] - ar[i]);
        rlim = ((ar[idx] + ar[i] - 1) >> 1);
      }
      stv.update(stv.rt, 0, Val, ar[i], i);
      for (; c <= m && qs[c].r == i; c++)
        qs[c].res = min(qs[c].res, st.query(st.rt, 1, n, qs[c].l));
    }
    for (int i = 1; i <= n; i++) ar[i] = Val - ar[i];
  }
  for (int i = 1; i <= m; i++)
    while (qs[i].id != i) swap(qs[i], qs[qs[i].id]);
  for (int i = 1; i <= m; i++) printf("%d ", qs[i].res);
}
int main() {
  init();
  solve();
  return 0;
}
