#include <bits/stdc++.h>
inline long long rd() {
  long long _x = 0;
  int _ch = getchar(), _f = 1;
  for (; !isdigit(_ch) && (_ch != '-') && (_ch != EOF); _ch = getchar())
    ;
  if (_ch == '-') {
    _f = 0;
    _ch = getchar();
  }
  for (; isdigit(_ch); _ch = getchar()) _x = _x * 10 + _ch - '0';
  return _f ? _x : -_x;
}
void write(long long _x) {
  if (_x >= 10)
    write(_x / 10), putchar(_x % 10 + '0');
  else
    putchar(_x + '0');
}
inline void wrt(long long _x, char _p) {
  if (_x < 0) putchar('-'), _x = -_x;
  write(_x);
  if (_p) putchar(_p);
}
int n, m;
struct node {
  int ans;
  std::vector<int> vt;
  inline int getans(int c) {
    std::vector<int>::iterator it = std::lower_bound(vt.begin(), vt.end(), c);
    int r = 1e9;
    if (it != vt.end()) {
      r = *it - c;
    }
    if (it != vt.begin()) {
      --it;
      r = std::min(r, c - *it);
    }
    return r;
  }
} tr[100005 << 2];
int a[100005];
void build(int pos, int l, int r) {
  tr[pos].ans = 1e9;
  if (l == r) {
    tr[pos].vt.push_back(a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(pos << 1, l, mid), build(pos << 1 | 1, mid + 1, r);
  for (auto i : tr[pos << 1 | 1].vt) {
    tr[pos].vt.push_back(i);
  }
  for (auto i : tr[pos << 1].vt) {
    tr[pos].vt.push_back(i);
  }
  std::sort(tr[pos].vt.begin(), tr[pos].vt.end());
}
int right;
void update(int pos, int l, int r, int v, int qr) {
  if (r <= qr) {
    int x = tr[pos].getans(v);
    tr[pos].ans = std::min(tr[pos].ans, x);
    if (x >= right || l == r) return;
  }
  int mid = (l + r) >> 1;
  if (qr > mid) update(pos << 1 | 1, mid + 1, r, v, qr);
  update(pos << 1, l, mid, v, qr);
  tr[pos].ans = std::min(tr[pos << 1].ans, tr[pos << 1 | 1].ans);
  right = std::min(right, tr[pos].ans);
}
int query(int pos, int l, int r, int ql, int qr) {
  if (r < ql || l > qr) return 1e9;
  if (ql <= l && r <= qr) return tr[pos].ans;
  int mid = (l + r) >> 1;
  return std::min(query(pos << 1, l, mid, ql, qr),
                  query(pos << 1 | 1, mid + 1, r, ql, qr));
}
int Ans[100005 * 3];
std::vector<std::pair<int, int> > vt[100005];
int main() {
  n = rd();
  for (int i = 1; i <= n; i++) {
    a[i] = rd();
  }
  m = rd();
  for (int i = 1; i <= m; i++) {
    int x = rd(), y = rd();
    vt[y].push_back(std::make_pair(x, i));
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    right = 1e9;
    if (i > 1) update(1, 1, n, a[i], i - 1);
    for (auto j : vt[i]) {
      Ans[j.second] = query(1, 1, n, j.first, i);
    }
  }
  for (int i = 1; i <= m; i++) {
    wrt(Ans[i], '\n');
  }
}
