#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int maxn = 100100;
const int maxm = 300100;
int n;
int a[maxn + 5];
struct node {
  node *c[2];
  int Min;
  vector<pair<int, int> > all;
  node() : Min(oo) { memset(c, 0, sizeof c); }
};
node nd[(maxn << 1) + 5];
int nd_cur = 0;
inline node *newnode() { return nd + (nd_cur++); }
void build(node *&rt, int l, int r) {
  rt = newnode();
  if (r - l <= 1) {
    rt->all.push_back(make_pair(a[l], 0));
    rt->all.push_back(make_pair(oo, 0));
    return;
  }
  int mid = (l + r) >> 1;
  build(rt->c[0], l, mid);
  build(rt->c[1], mid, r);
  int u = 0, v = 0;
  int cur = 0;
  for (int i = (0), i_end_ = ((int((rt->c[0]->all).size())) +
                              (int((rt->c[1]->all).size())) - 2);
       i < i_end_; ++i) {
    if (rt->c[1]->all[v].first < rt->c[0]->all[u].first)
      rt->all.push_back(make_pair(rt->c[1]->all[v++].first, cur));
    else
      rt->all.push_back(make_pair(rt->c[0]->all[u++].first, cur++));
  }
  rt->all.push_back(make_pair(oo, cur));
}
int seg_x, seg_y, seg_z, seg_ret;
void add(node *rt, int l, int r, int p) {
  if (r <= seg_x + 1) return;
  if (r - l <= 1) {
    chkmin(rt->Min, abs(a[l] - a[seg_x]));
    chkmin(seg_z, rt->Min);
    return;
  }
  {
    int tmp = oo;
    if (p < (int((rt->all).size())) - 1)
      chkmin(tmp, rt->all[p].first - a[seg_x]);
    if (p) chkmin(tmp, a[seg_x] - rt->all[p - 1].first);
    if (tmp >= seg_z) {
      chkmin(seg_z, rt->Min);
      return;
    }
  }
  int mid = (l + r) >> 1;
  add(rt->c[0], l, mid, rt->all[p].second);
  add(rt->c[1], mid, r, p - rt->all[p].second);
  rt->Min = seg_z;
}
void query(node *rt, int l, int r) {
  if (seg_x <= l && r <= seg_y) {
    chkmin(seg_ret, rt->Min);
    return;
  }
  int mid = (l + r) >> 1;
  if (seg_x < mid) query(rt->c[0], l, mid);
  if (seg_y > mid) query(rt->c[1], mid, r);
}
node *rt;
int qn;
int pos[maxm + 5];
pair<int, int> q[maxm + 5];
int ans[maxm + 5];
int main() {
  scanf("%d", &n);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i) scanf("%d", a + i);
  build(rt, 0, n);
  scanf("%d", &qn);
  for (int i = (0), i_end_ = (qn); i < i_end_; ++i) {
    pos[i] = i;
    scanf("%d%d", &q[i].first, &q[i].second), --q[i].first;
  }
  sort(pos, pos + qn,
       [&](int first, int second) { return q[first] > q[second]; });
  int j = 0;
  for (int i = n - 1; i >= 0; --i) {
    seg_x = i;
    seg_z = oo;
    add(rt, 0, n,
        lower_bound((rt->all).begin(), (rt->all).end(), make_pair(a[i], 0)) -
            rt->all.begin());
    seg_x = i + 1;
    while (j < qn && q[pos[j]].first == i) {
      seg_y = q[pos[j]].second;
      seg_ret = oo;
      query(rt, 0, n);
      ans[pos[j]] = seg_ret;
      ++j;
    }
  }
  for (int i = (0), i_end_ = (qn); i < i_end_; ++i) printf("%d\n", ans[i]);
  return 0;
}
