#include <bits/stdc++.h>
using namespace std;
int n, m, tot;
int a[300009], ans[300009], c[300009], A[300009], rt[300009];
struct data {
  int ls, rs, sum, ma;
  data() { ls = rs = sum = ma = 0; }
} s[300009 * 30];
struct que {
  int l, id;
  que(int l = 0, int id = 0) : l(l), id(id) {}
};
vector<que> q[300009];
int lowbit(int x) { return x & (-x); }
void upd(int x, int v) {
  for (int i = x; i; i -= lowbit(i)) c[i] = min(c[i], v);
}
int ask(int x) {
  int re = 2000000000;
  for (int i = x; i <= n; i += lowbit(i)) re = min(re, c[i]);
  return re;
}
int update(int x, int l, int r, int p, int v) {
  int now = ++tot;
  s[now] = s[x];
  s[now].sum += 1;
  s[now].ma = max(s[now].ma, v);
  if (l == r) return now;
  int mid = (l + r) >> 1;
  if (p <= mid) {
    s[now].ls = update(s[x].ls, l, mid, p, v);
  } else {
    s[now].rs = update(s[x].rs, mid + 1, r, p, v);
  }
  return now;
}
int get_rank(int x, int l, int r, int p) {
  if (!x) return 0;
  if (l == r) {
    return p >= l ? s[x].sum : 0;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) {
    return get_rank(s[x].ls, l, mid, p);
  } else {
    return s[s[x].ls].sum + get_rank(s[x].rs, mid + 1, r, p);
  }
}
int get_mx(int x, int l, int r, int L, int R) {
  if (!x) return -1000000000;
  if (l >= L && r <= R) return s[x].ma;
  int mid = (l + r) >> 1, re = -1000000000;
  if (L <= mid) re = max(re, get_mx(s[x].ls, l, mid, L, R));
  if (R > mid) re = max(re, get_mx(s[x].rs, mid + 1, r, L, R));
  return re;
}
int get_num(int x, int l, int r, int kth) {
  if (!x) return -1000000000;
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1, re = s[s[x].ls].sum;
  if (kth <= re) {
    return get_num(s[x].ls, l, mid, kth);
  } else {
    return get_num(s[x].rs, mid + 1, r, kth - re);
  }
}
void sol() {
  for (int i = 1; i <= n; ++i) A[i] = a[i];
  for (int i = 0; i < 300009; ++i) c[i] = 2000000000;
  for (int i = 1; i <= n; ++i) rt[i] = 0;
  for (int i = 1; i <= tot; ++i) s[i] = data();
  tot = 0, sort(A + 1, A + 1 + n);
  for (int i = 1; i <= n; ++i) {
    int v = 1000000000, r = i - 1, flag = 0;
    while (r >= 1) {
      int ra = get_rank(rt[r], -1000000000, 1000000000, a[i] - 1);
      int z = get_num(rt[r], -1000000000, 1000000000, ra + 1);
      if (z < a[i] || (flag && (z >= v))) break;
      int cur = get_mx(rt[r], -1000000000, 1000000000, z, v);
      upd(cur, a[cur] - a[i]);
      r = cur - 1, v = (a[cur] + a[i]) >> 1, flag = 1;
      if (((a[cur] + a[i]) % 2) && v < 0) ++v;
    }
    rt[i] = update(rt[i - 1], -1000000000, 1000000000, a[i], i);
    for (int j = 0; j < q[i].size(); ++j) {
      ans[q[i][j].id] = min(ans[q[i][j].id], ask(q[i][j].l));
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  scanf("%d", &m);
  int x, y, z;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    q[y].push_back(que(x, i));
    ans[i] = 2000000000;
  }
  sol();
  for (int i = 1; i <= n; ++i) a[i] = -a[i];
  sol();
  for (int i = 1; i <= m; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
