#include <bits/stdc++.h>
using namespace std;
const int maplacen = 100005;
int n, m, *a[400001], b[100001], pool[2000000], *pre = pool;
char c;
inline void read(int &a) {
  a = 0;
  do c = getchar();
  while (c < '0' || c > '9');
  while (c <= '9' && c >= '0') a = (a << 3) + (a << 1) + c - '0', c = getchar();
}
struct data {
  int l, r, no;
  bool operator<(const data &a) const { return r < a.r; }
} d[400001];
struct Node {
  int l, r, mn;
} T[400001];
int Ans[400001];
int rpos, MIN;
void Min(int &x, int y) {
  if (x > y) x = y;
}
void build(int place, int l, int r) {
  T[place].mn = 1 << 30;
  T[place].l = l, T[place].r = r;
  if (l == r) return;
  int sz = r - l + 1, i, mid = (l + r) >> 1;
  a[place] = pre;
  pre += sz;
  for (i = 0; i < sz; i++) a[place][i] = b[i + l];
  sort(a[place], a[place] + sz);
  build(place << 1, l, mid);
  build(place << 1 | 1, mid + 1, r);
}
void Update(int place) {
  if (T[place].l == T[place].r) {
    Min(T[place].mn, abs(b[rpos] - b[T[place].l])), Min(MIN, T[place].mn);
    return;
  }
  if (T[place].r < rpos) {
    int pos =
        lower_bound(a[place], a[place] + T[place].r - T[place].l + 1, b[rpos]) -
        a[place];
    if ((pos == 0 || b[rpos] - a[place][pos - 1] >= MIN) &&
        (pos == T[place].r - T[place].l + 1 ||
         a[place][pos] - b[rpos] >= MIN)) {
      Min(MIN, T[place].mn);
      return;
    }
  }
  int mid = T[place << 1].r;
  if (rpos - 1 > mid) Update(place << 1 | 1);
  Update(place << 1);
  T[place].mn = min(T[place << 1].mn, T[place << 1 | 1].mn);
}
int Query(int place, int l, int r) {
  if (l <= T[place].l && T[place].r <= r) return T[place].mn;
  int mid = T[place << 1].r, res = 1 << 30;
  if (l <= mid) Min(res, Query(place << 1, l, r));
  if (r > mid) Min(res, Query(place << 1 | 1, l, r));
  return res;
}
int main() {
  int i;
  for (read(n), i = 1; i <= n; read(b[i++]))
    ;
  for (read(m), i = 1; i <= m; i++) read(d[i].l), read(d[i].r), d[i].no = i;
  sort(d + 1, d + m + 1);
  build(1, 1, n);
  for (rpos = i = 1; i <= m; i++) {
    while (rpos < d[i].r) {
      ++rpos;
      MIN = 1 << 30;
      Update(1);
    }
    Ans[d[i].no] = Query(1, d[i].l, d[i].r - 1);
  }
  for (i = 1; i <= m; i++) printf("%d\n", Ans[i]);
  return 0;
}
