#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  int x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(int a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(int a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  write(a);
  puts("");
}
const int N = 100005, oo = 1000000005;
int ans[N * 3], d, n, m, dq, tree[N << 2], a[N];
vector<int> v[N << 2];
struct data {
  int l, r, id;
} q[N * 3];
inline bool cmp(data a, data b) { return a.r < b.r; }
void build(int l, int r, int nod) {
  tree[nod] = oo;
  for (int i = l; i <= r; i++) {
    v[nod].push_back(a[i]);
  }
  sort(v[nod].begin(), v[nod].end());
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, nod << 1);
  build(mid + 1, r, nod << 1 | 1);
}
inline int ask(int l, int r, int i, int j, int nod) {
  if (l == i && j == r) return tree[nod];
  int mid = (l + r) >> 1;
  if (j <= mid)
    return ask(l, mid, i, j, nod << 1);
  else if (i > mid)
    return ask(mid + 1, r, i, j, nod << 1 | 1);
  int left = ask(l, mid, i, mid, nod << 1);
  int right = ask(mid + 1, r, mid + 1, j, nod << 1 | 1);
  return min(left, right);
}
inline void insert(int l, int r, int pos, int nod) {
  if (l >= pos) return;
  if (l == r) {
    d = min(d, tree[nod] = min(tree[nod], abs(a[l] - a[pos])));
    return;
  }
  int t = lower_bound(v[nod].begin(), v[nod].end(), a[pos]) - v[nod].begin(),
      ans = oo;
  if (t < v[nod].size()) ans = min(v[nod][t] - a[pos], ans);
  if (t) ans = min(a[pos] - v[nod][t - 1], ans);
  if (ans >= d) {
    d = ask(l, r, l, min(pos, r), nod);
    return;
  }
  int mid = (l + r) >> 1;
  insert(mid + 1, r, pos, nod << 1 | 1);
  insert(l, mid, pos, nod << 1);
  tree[nod] = min(tree[nod], min(tree[nod << 1], tree[nod << 1 | 1]));
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  build(1, n, 1);
  m = read();
  for (int i = 1; i <= m; i++) {
    q[i].l = read();
    q[i].r = read();
    q[i].id = i;
  }
  sort(&q[1], &q[m + 1], cmp);
  for (int i = 1; i <= m; i++) {
    while (dq < q[i].r) d = oo, insert(1, n, ++dq, 1);
    ans[q[i].id] = ask(1, n, q[i].l, q[i].r, 1);
  }
  for (int i = 1; i <= m; i++) writeln(ans[i]);
}
