#include <bits/stdc++.h>
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const double eps = 1e-9;
using namespace std;
int tree[MAXN], ans[MAXN], n;
int arr[MAXN], BIT[MAXN], cp[MAXN];
vector<pair<int, int> > qry[MAXN];
void build(int l, int r, int k) {
  tree[k] = n;
  if (l == r) return;
  int m = (l + r) >> 1;
  build(l, m, k << 1);
  build(m + 1, r, k << 1 | 1);
}
void upd(int l, int r, int k, int val, int ind) {
  if (val < arr[l] || arr[r] < val) return;
  tree[k] = min(tree[k], ind);
  if (l == r) return;
  int m = (l + r) >> 1;
  upd(l, m, k << 1, val, ind);
  upd(m + 1, r, k << 1 | 1, val, ind);
}
int query(int l, int r, int k, int a, int b) {
  if (a > arr[r] || arr[l] > b) return INF;
  if (a <= arr[l] && arr[r] <= b) return tree[k];
  int m = (l + r) >> 1;
  return min(query(l, m, k << 1, a, b), query(m + 1, r, k << 1 | 1, a, b));
}
void add(int ind, int val) {
  ++ind;
  while (ind <= n) {
    BIT[ind] = min(BIT[ind], val);
    ind += ind & -ind;
  }
}
int sum(int ind) {
  ++ind;
  int ret = INF;
  while (ind > 0) {
    ret = min(ret, BIT[ind]);
    ind -= ind & -ind;
  }
  return ret;
}
int main() {
  int q, m;
  scanf("%d", &(n));
  for (int i = 0; i < n; i++) {
    scanf("%d", &(arr[i]));
    cp[i] = arr[i];
    BIT[i] = INF;
  }
  sort(arr, arr + n);
  m = unique(arr, arr + n) - arr;
  cp[n] = 0;
  BIT[n] = BIT[n + 1] = BIT[n + 2] = INF;
  build(0, n - 1, 1);
  scanf("%d", &(q));
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d", &(l)), scanf("%d", &(r));
    l--, r--;
    qry[l].push_back({r, i});
  }
  for (int i = n - 1; i >= 0; i--) {
    int lo = 0, hi = INF;
    while (hi >= cp[i]) {
      int ind = query(0, m - 1, 1, cp[i], hi);
      add(ind, cp[ind] - cp[i]);
      if (hi == cp[i]) break;
      hi = (hi + cp[i]) >> 1;
    }
    while (lo <= cp[i]) {
      int ind = query(0, m - 1, 1, lo, cp[i]);
      add(ind, cp[i] - cp[ind]);
      if (lo == cp[i]) break;
      lo = (lo + cp[i] + 1) >> 1;
    }
    upd(0, m - 1, 1, cp[i], i);
    for (pair<int, int> cur : qry[i]) ans[cur.second] = sum(cur.first);
  }
  for (int i = 0; i < q; i++) printf("%d\n", (ans[i]));
  return 0;
}
