#include <bits/stdc++.h>
using namespace std;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& rout, pair<T1, T2> pair) {
  return rout << "(" << pair.first << ", " << pair.second << ")";
}
const int INF = 2e9;
struct iT {
  int n;
  vector<int> vals;
  iT(int _n) {
    n = 1;
    while (n < _n) n *= 2;
    vals = vector<int>(2 * n, INF);
  }
  void set(int i, int v) {
    i += n;
    while (i) {
      mini(vals[i], v);
      i /= 2;
    }
  }
  int get(int i) {
    i += n;
    int res = vals[i];
    while (i > 1) {
      if (i % 2 == 1) mini(res, vals[i - 1]);
      i /= 2;
    }
    return res;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n;
  cin >> n;
  vector<int> a(n);
  int lg = 30;
  for (int i = 0; i < (n); ++i) cin >> a[i];
  vector<map<int, int>> M(lg);
  vector<vector<pair<int, int>>> evs(n);
  for (int i = 0; i < (n); ++i) {
    vector<int> cands;
    for (int j = 0; j < (lg); ++j) {
      int w = a[i] >> j;
      auto it = M[j].lower_bound(w);
      auto jt = it;
      for (int _ = 0; _ < (3); ++_) {
        if (it != M[j].end()) {
          cands.push_back(it->second);
          ++it;
        }
      }
      for (int _ = 0; _ < (2); ++_) {
        if (jt != M[j].begin()) {
          --jt;
          cands.push_back(jt->second);
        }
      }
      M[j][w] = i;
    }
    sort((cands).begin(), (cands).end());
    reverse((cands).begin(), (cands).end());
    int val = INF;
    for (auto c : cands) {
      int d = a[c] - a[i];
      if (d < 0) d *= -1;
      if (d < val) {
        evs[c].push_back(make_pair(i, d));
        val = d;
      }
    }
  }
  vector<vector<pair<int, int>>> queries(n);
  int m;
  cin >> m;
  for (int t = 0; t < (m); ++t) {
    int i, j;
    cin >> i >> j;
    --i;
    --j;
    queries[i].push_back(make_pair(j, t));
  }
  vector<int> ans(m);
  iT T(n);
  for (int x = (n - 1); x >= (0); --x) {
    for (auto e : evs[x]) {
      T.set(e.first, e.second);
    }
    for (auto e : queries[x]) {
      ans[e.second] = T.get(e.first);
    }
  }
  for (int i = 0; i < (m); ++i) cout << ans[i] << endl;
  return 0;
}
