#include <bits/stdc++.h>
using namespace std;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
const int N = 300100, inf = 1e9 + 10;
int tree[N * 4], mx[4 * N];
int lazy[4 * N];
void build() {
  for (int i = 0; i < 4 * N; i++) {
    tree[i] = lazy[i] = inf;
    mx[i] = -1;
  }
}
inline void flush(int no, int i, int j) {
  if (lazy[no] != inf) {
    tree[no] = min(tree[no], lazy[no]);
    if (i != j) {
      lazy[no << 1] = min(lazy[no << 1], lazy[no]);
      lazy[no << 1 | 1] = min(lazy[no << 1 | 1], lazy[no]);
    }
    lazy[no] = inf;
  }
}
void upd_mn(int no, int i, int j, int a, int b, int val) {
  flush(no, i, j);
  if (i > j or i > b or j < a) return;
  if (a <= i and j <= b) {
    lazy[no] = val;
    flush(no, i, j);
    return;
  }
  int m = i + j >> 1, l = no << 1, r = no << 1 | 1;
  upd_mn(l, i, m, a, b, val);
  upd_mn(r, m + 1, j, a, b, val);
  tree[no] = min(tree[l], tree[r]);
}
int get_mn(int no, int i, int j, int pos) {
  flush(no, i, j);
  if (i == j) return tree[no];
  int m = i + j >> 1, l = no << 1, r = no << 1 | 1;
  if (pos <= m)
    return get_mn(l, i, m, pos);
  else
    return get_mn(r, m + 1, j, pos);
}
void upd_mx(int no, int i, int j, int p, int v) {
  if (i == j) {
    mx[no] = v;
    return;
  }
  int m = i + j >> 1, l = no << 1, r = no << 1 | 1;
  if (p <= m)
    upd_mx(l, i, m, p, v);
  else
    upd_mx(r, m + 1, j, p, v);
  mx[no] = max(mx[l], mx[r]);
}
int get_mx(int no, int i, int j, int a, int b) {
  if (i > b or j < a or i > j) return 0;
  if (a <= i and j <= b) return mx[no];
  int m = i + j >> 1, l = no << 1, r = no << 1 | 1;
  return max(get_mx(l, i, m, a, b), get_mx(r, m + 1, j, a, b));
}
int a[N];
int ans[N];
vector<pair<int, int> > go[N];
int n;
int comprime[N];
int sefude[N];
void SOLVE() {
  build();
  vector<int> aux;
  stack<int> st;
  for (int i = 1; i <= n; i++) {
    while (st.size() and a[st.top()] < a[i]) st.pop();
    aux.push_back(a[i]);
    if (st.size())
      sefude[i] = st.top();
    else
      sefude[i] = -1;
    st.push(i);
  }
  sort(aux.begin(), aux.end());
  aux.erase(unique(aux.begin(), aux.end()), aux.end());
  for (int i = 1; i <= n; i++) {
    comprime[i] = lower_bound(aux.begin(), aux.end(), a[i]) - aux.begin() + 1;
  }
  for (int i = 1; i <= n; i++) {
    int pos = sefude[i];
    if (pos > 0) {
      upd_mn(1, 1, n, 1, sefude[i], a[pos] - a[i]);
      int cur = (a[pos] + a[i] + 1) / 2 - 1;
      int counter = 0;
      while (cur > 0) {
        int nxt = lower_bound(aux.begin(), aux.end(), cur) - aux.begin() + 1;
        if (aux[nxt - 1] > cur) nxt--;
        if (aux[nxt] < a[i]) break;
        int pega = get_mx(1, 1, n, comprime[i], nxt);
        if (a[pega] < a[i]) break;
        int delta = a[pega] - a[i];
        upd_mn(1, 1, n, 1, pega, delta);
        cur = (a[pega] + a[i] + 1) / 2 - 1;
        counter++;
        assert(counter <= 30);
      }
    }
    for (auto it : go[i]) {
      ans[it.second] = min(ans[it.second], get_mn(1, 1, n, it.first));
    }
    upd_mx(1, 1, n, comprime[i], i);
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    ans[i] = inf;
    int l, r;
    cin >> l >> r;
    go[r].push_back(pair<int, int>(l, i));
  }
  SOLVE();
  for (int i = 1; i <= n; i++) a[i] = inf - a[i];
  SOLVE();
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << "\n";
  }
}
