#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005, maxm = 300005, inf = 0x7fffffff;
struct data {
  int l, r, id;
  friend bool operator<(data a, data b) { return a.r < b.r; }
} ask[maxm];
int lc[maxn << 2], rc[maxn << 2], hh[maxn << 2], rt, np;
int ans[maxm], a[maxn];
int n, m, mi;
set<int> e[maxn << 2];
void initial() {
  memset(lc, 0, sizeof(lc));
  memset(rc, 0, sizeof(rc));
  memset(hh, 0, sizeof(hh));
  rt = np = 0;
}
void pushup(int now) { hh[now] = min(hh[lc[now]], hh[rc[now]]); }
void build(int &now, int L, int R) {
  now = ++np, hh[now] = inf;
  if (L == R) return;
  int m = L + R >> 1;
  build(lc[now], L, m);
  build(rc[now], m + 1, R);
}
void modify(int now, int L, int R, int qr, int d) {
  if (L == R) {
    if (L == qr) return;
    hh[now] = min(hh[now], abs(d - a[L]));
    mi = min(mi, hh[now]);
    return;
  }
  if (R <= qr) {
    set<int>::iterator it = e[now].lower_bound(d);
    if ((it == e[now].end() || abs(*it - d) >= mi) &&
        (it == e[now].begin() || abs(*(--it) - d) >= mi)) {
      mi = min(mi, hh[now]);
      return;
    }
    int m = L + R >> 1;
    modify(rc[now], m + 1, R, qr, d);
    modify(lc[now], L, m, qr, d);
    pushup(now);
    return;
  }
  int m = L + R >> 1;
  if (qr <= m)
    modify(lc[now], L, m, qr, d);
  else {
    modify(rc[now], m + 1, R, qr, d);
    modify(lc[now], L, m, qr, d);
  }
  pushup(now);
}
void insert(int now, int L, int R, int x, int y) {
  e[now].insert(y);
  if (L == R) return;
  int m = L + R >> 1;
  if (x <= m)
    insert(lc[now], L, m, x, y);
  else
    insert(rc[now], m + 1, R, x, y);
}
int query(int now, int L, int R, int x, int y) {
  if (L == x && R == y) return hh[now];
  int m = L + R >> 1;
  if (y <= m)
    return query(lc[now], L, m, x, y);
  else if (x > m)
    return query(rc[now], m + 1, R, x, y);
  else
    return min(query(lc[now], L, m, x, m), query(rc[now], m + 1, R, m + 1, y));
}
int main() {
  initial();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &ask[i].l, &ask[i].r);
    ask[i].id = i;
  }
  sort(ask + 1, ask + m + 1);
  build(rt, 1, n);
  int r = 0;
  for (int i = 1; i <= m; i++) {
    while (r < ask[i].r) {
      r++, mi = inf;
      modify(rt, 1, n, r, a[r]);
      insert(rt, 1, n, r, a[r]);
    }
    ans[ask[i].id] = query(rt, 1, n, ask[i].l, ask[i].r);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
