#include <bits/stdc++.h>
using namespace std;
inline void read(int& x) {
  char c = getchar();
  x = 0;
  while (c < '0' || c > '9') c = getchar();
  while (c <= '9' && c >= '0') x = x * 10 + c - 48, c = getchar();
  return;
}
inline void write(int x) {
  if (!x) {
    putchar('0');
    putchar('\n');
    return;
  }
  int num = 0;
  char c[15];
  while (x) c[++num] = (x % 10) + 48, x /= 10;
  while (num) putchar(c[num--]);
  putchar('\n');
  return;
}
inline int min(int a, int b) {
  if (a < b) return a;
  return b;
}
const int maxn = int(3e5) + 10;
const int K = 31;
const int INF = int(1e9) + 10;
struct tri {
  int a, b, c;
} q[maxn];
int top = 0;
inline bool cmp(const tri& A, const tri& B) { return A.b < B.b; }
int n, qnum;
int b[maxn];
int ans[maxn];
struct Node {
  int* a;
  int ans;
} node[maxn * 4];
int* getnew(int siz) { return new int[siz]; }
void build(int k, int l, int r) {
  node[k].a = getnew(r - l + 1);
  if (l == r) {
    node[k].a[0] = b[l];
    node[k].ans = INF;
    return;
  }
  int mid = (l + r) >> 1, siz = r - l + 1;
  build((k << 1), l, mid);
  build(((k << 1) ^ 1), mid + 1, r);
  std::merge(node[(k << 1)].a, node[(k << 1)].a + mid - l + 1,
             node[((k << 1) ^ 1)].a, node[((k << 1) ^ 1)].a + r - mid,
             node[k].a);
  int res = INF;
  for (int i = 1; i < siz; i++) res = min(res, node[k].a[i] - node[k].a[i - 1]);
  node[k].ans = res;
  return;
}
int query(int, int, int, int, int);
void update(int k, int l, int r, int to, int x, int& d) {
  if (l == r) {
    node[k].ans = min(node[k].ans, abs(x - node[k].a[0]));
    d = min(d, node[k].ans);
    return;
  }
  int mid = (l + r) >> 1, siz = r - l + 1;
  int* it = std::lower_bound(node[k].a, node[k].a + siz, x);
  if ((it == node[k].a + siz || *it >= x + d) &&
      (it == node[k].a || *(it - 1) <= x - d)) {
    d = min(d, query(k, l, r, l, to));
    return;
  }
  if (to > mid) {
    update(((k << 1) ^ 1), mid + 1, r, to, x, d),
        update((k << 1), l, mid, mid, x, d);
  } else
    update((k << 1), l, mid, to, x, d);
  node[k].ans =
      min(node[k].ans, min(node[(k << 1)].ans, node[((k << 1) ^ 1)].ans));
  return;
}
int query(int k, int l, int r, int x, int y) {
  if (l == x && r == y) return node[k].ans;
  int mid = (l + r) >> 1;
  if (y <= mid)
    return query((k << 1), l, mid, x, y);
  else if (x > mid)
    return query(((k << 1) ^ 1), mid + 1, r, x, y);
  else
    return min(query((k << 1), l, mid, x, mid),
               query(((k << 1) ^ 1), mid + 1, r, mid + 1, y));
}
int main() {
  read(n);
  for (int i = 0; i < n; i++) read(b[i]);
  read(qnum);
  for (int i = 0; i < qnum; i++) {
    int l, r;
    read(l), read(r);
    l--, r--;
    const int K = 31;
    if (r - l <= K) {
      int cur[K + 1], siz = r - l + 1;
      for (int j = l; j <= r; j++) cur[j - l] = b[j];
      sort(cur, cur + siz);
      int res = INF;
      for (int j = 1; j < siz; j++) res = min(res, cur[j] - cur[j - 1]);
      ans[i] = res;
    } else
      q[top++] = {l, r, i};
  }
  sort(q, q + top, cmp);
  int curr = 0;
  build(1, 0, n - 1);
  for (int k = 0; k < top; k++) {
    int l = q[k].a, r = q[k].b, index = q[k].c;
    while (curr < r) {
      ++curr;
      int d = INF;
      update(1, 0, n - 1, curr - 1, b[curr], d);
    }
    ans[index] = query(1, 0, n - 1, l, r);
  }
  for (int i = 0; i < qnum; i++) write(ans[i]);
  return 0;
}
