#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
template <typename Comp>
struct segment_tree {
  int n, neutral;
  Comp cmp;
  vector<int> nodes;
  segment_tree(int n, int neutral)
      : n(n), neutral(neutral), cmp(Comp()), nodes(2 * n, neutral) {}
  int merge(int x, int y) { return cmp(x, y) ? x : y; }
  void update(int p, int v) {
    p += n;
    nodes[p] = merge(nodes[p], v);
    while (p /= 2) nodes[p] = merge(nodes[2 * p], nodes[2 * p + 1]);
  }
  int query(int l, int r) {
    int ans = neutral;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) ans = merge(ans, nodes[l++]);
      if (r & 1) ans = merge(ans, nodes[--r]);
    }
    return ans;
  }
};
struct int_mapper {
  vector<int> values;
  int_mapper(vector<int> _values) : values(_values) {
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
  }
  int operator[](int val) const {
    auto it = lower_bound(values.begin(), values.end(), val);
    return distance(values.begin(), it);
  }
  size_t size() const { return values.size(); }
};
int main() {
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  for (int &x : a) scanf("%d", &x);
  int m;
  scanf("%d", &m);
  vector<int> l(m), ans(m, oo);
  vector<vector<int>> queries(n);
  for (int i = 0; i < m; --l[i++]) {
    int r;
    scanf("%d%d", &l[i], &r);
    queries[--r].push_back(i);
  }
  for (int it : {0, 1}) {
    int_mapper mapper(a);
    segment_tree<less<int>> tree(a.size(), oo);
    segment_tree<greater<int>> positions(mapper.size(), -oo);
    for (int i = 0; i < n; ++i) {
      int j = positions.query(mapper[a[i]], mapper.size());
      while (j >= 0) {
        tree.update(j, a[j] - a[i]);
        if (a[j] == a[i]) break;
        int nj = positions.query(mapper[a[i]], mapper[(a[i] + a[j] + 1) / 2]);
        if (nj == j) break;
        j = nj;
      }
      positions.update(mapper[a[i]], i);
      for (int q : queries[i]) ans[q] = min(ans[q], tree.query(l[q], i + 1));
    }
    for (int &x : a) x = 1000000000 - x;
    int mn = *min_element(a.begin(), a.end());
    for (int &x : a) x -= mn;
  }
  for (int x : ans) printf("%d\n", x);
  return 0;
}
