#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1 << 17;
const int INF = 1.05e9;
template <class Comp>
struct segtree {
  Comp comp;
  int ident;
  int tree[2 * MAXN];
  int lazy[2 * MAXN];
  int func(int x, int y) { return comp(x, y) ? x : y; }
  segtree(int _ident) {
    ident = _ident;
    for (int i = 0; i < 2 * MAXN; i++) {
      tree[i] = lazy[i] = ident;
    }
  }
  void put(int cur, int v) {
    tree[cur] = func(tree[cur], v);
    lazy[cur] = func(lazy[cur], v);
  }
  void down(int cur) {
    if (lazy[cur] != ident) {
      put(2 * cur, lazy[cur]);
      put(2 * cur + 1, lazy[cur]);
      lazy[cur] = ident;
    }
  }
  void update(int a, int b, int v, int cur = 1, int lt = 0, int rt = MAXN) {
    if (rt <= a || b <= lt) {
      return;
    }
    if (a <= lt && rt <= b) {
      put(cur, v);
      return;
    }
    down(cur);
    int mid = (lt + rt) / 2;
    update(a, b, v, 2 * cur, lt, mid);
    update(a, b, v, 2 * cur + 1, mid, rt);
    tree[cur] = func(tree[2 * cur], tree[2 * cur + 1]);
  }
  int query(int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
    if (rt <= a || b <= lt) {
      return ident;
    }
    if (a <= lt && rt <= b) {
      return tree[cur];
    }
    down(cur);
    int mid = (lt + rt) / 2;
    return func(query(a, b, 2 * cur, lt, mid),
                query(a, b, 2 * cur + 1, mid, rt));
  }
};
int N, M;
int A[MAXN];
vector<int> vals;
vector<pair<int, int>> qu[MAXN];
int ans[3 * MAXN];
segtree<less<int>> segans(INF);
segtree<greater<int>> segind(0);
int atmost(int x) {
  return upper_bound((vals).begin(), (vals).end(), x) - vals.begin() - 1;
}
int atleast(int x) {
  return lower_bound((vals).begin(), (vals).end(), x) - vals.begin();
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
  }
  vals.assign(A + 1, A + N + 1);
  sort((vals).begin(), (vals).end());
  vals.resize(unique((vals).begin(), (vals).end()) - vals.begin());
  scanf("%d", &M);
  for (int i = 1; i <= M; i++) {
    int lt, rt;
    scanf("%d %d", &lt, &rt);
    qu[rt].push_back({lt, i});
  }
  for (int i = 1; i <= N; i++) {
    int ix = atmost(A[i]);
    int gr = 1e9 + 10;
    while (true) {
      int ind = segind.query(ix, atmost(gr) + 1);
      if (ind == 0) {
        break;
      }
      int val = A[ind];
      segans.update(1, ind + 1, val - A[i]);
      int pgr = gr;
      gr = (val + A[i]) / 2 + 1;
      if (pgr == gr) {
        break;
      }
    }
    int ls = 0;
    while (true) {
      int ind = segind.query(atleast(ls), ix + 1);
      if (ind == 0) {
        break;
      }
      int val = A[ind];
      segans.update(1, ind + 1, A[i] - val);
      int pls = ls;
      ls = (A[i] + val) / 2 + 1;
      if (pls == ls) {
        break;
      }
    }
    segind.update(ix, ix + 1, i);
    for (pair<int, int> p : qu[i]) {
      ans[p.second] = segans.query(p.first, p.first + 1);
    }
  }
  for (int i = 1; i <= M; i++) {
    printf("%d\n", ans[i]);
  }
}
