#include <bits/stdc++.h>
using namespace std;
struct wf {
  int l, r, w;
} tree[100005 << 2];
struct wff {
  int pos, l, r;
} q[100005 << 2];
vector<int> b[100005 << 2];
int a[100005 << 2], ans[100005 << 2], n, m, num, head;
void build(int l, int r, int root) {
  tree[root].w = 0x3f3f3f3f;
  tree[root].l = l;
  tree[root].r = r;
  for (int i = l; i <= r; i++) b[root].push_back(a[i]);
  sort(b[root].begin(), b[root].end());
  if (l == r) return;
  build(l, l + r >> 1, root << 1);
  build((l + r >> 1) + 1, r, root << 1 | 1);
}
void pushup(int root) {
  tree[root].w =
      min(tree[root].w, min(tree[root << 1].w, tree[root << 1 | 1].w));
  num = min(num, tree[root].w);
}
void change(int l, int x, int root) {
  if (tree[root].r <= l) {
    vector<int>::iterator it = upper_bound(b[root].begin(), b[root].end(), x);
    if (it != b[root].begin())
      tree[root].w = min(tree[root].w, abs(*(it - 1) - x));
    if (it != b[root].end()) tree[root].w = min(tree[root].w, abs(*it - x));
    if (tree[root].w >= num) return;
    if (tree[root].l == tree[root].r) {
      num = min(num, tree[root].w);
      return;
    }
  }
  if (l > (tree[root].l + tree[root].r) / 2) change(l, x, root << 1 | 1);
  change(l, x, root << 1);
  pushup(root);
}
int ask(int l, int r, int root) {
  if (tree[root].l > r || tree[root].r < l) return 0x3f3f3f3f;
  if (tree[root].l >= l && tree[root].r <= r) return tree[root].w;
  return min(ask(l, r, root << 1), ask(l, r, root << 1 | 1));
}
bool cmp(wff a, wff b) { return a.r < b.r; }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  build(1, n, 1);
  int l, r;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &l, &r);
    q[i] = (wff){i, l, r};
  }
  sort(q + 1, q + m + 1, cmp);
  head = 1;
  for (int i = 2; i <= n; i++) {
    num = 0x3f3f3f3f;
    change(i - 1, a[i], 1);
    while (q[head].r <= i && head <= m) {
      ans[q[head].pos] = ask(q[head].l, i, 1);
      ++head;
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
