#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5, MAXM = 3e5 + 5;
const int Inf = 1e9;
struct Query {
  int l, r, id;
} que[MAXM];
struct Node {
  int mn;
  set<int> d;
} tr[MAXN * 4];
int n, m, a[MAXN], ans[MAXM];
bool cmp(Query a, Query b) { return a.l > b.l; }
void build(int now, int l, int r) {
  tr[now].mn = Inf;
  for (int i = l; i <= r; i++) tr[now].d.insert(a[i]);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(now * 2, l, mid), build(now * 2 + 1, mid + 1, r);
}
int query(int now, int l, int r, int lx, int rx) {
  if (rx < l || lx > r) return Inf;
  if (l >= lx && r <= rx) return tr[now].mn;
  int mid = (l + r) >> 1;
  return min(query(now * 2, l, mid, lx, rx),
             query(now * 2 + 1, mid + 1, r, lx, rx));
}
void modify(int now, int l, int r, int lx, int rx, int num, int &mn) {
  if (rx < l || lx > r) return;
  if (l == r) {
    tr[now].mn = min(tr[now].mn, abs(a[l] - num));
    mn = min(mn, tr[now].mn);
    return;
  }
  set<int>::iterator p = tr[now].d.lower_bound(num);
  if ((p == tr[now].d.end() || (*p - num >= mn)) &&
      (p == tr[now].d.begin() || (num - *(--p) >= mn))) {
    mn = min(mn, query(now, l, r, lx, rx));
    return;
  }
  int mid = (l + r) >> 1;
  modify(now * 2, l, mid, lx, rx, num, mn),
      modify(now * 2 + 1, mid + 1, r, lx, rx, num, mn);
  tr[now].mn = min(tr[now * 2].mn, tr[now * 2 + 1].mn);
}
int main() {
  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", &que[i].l, &que[i].r);
    que[i].id = i;
  }
  sort(que + 1, que + m + 1, cmp);
  build(1, 1, n);
  for (int i = 1, lst = n, tmp; i <= m; i++) {
    for (; lst >= que[i].l; lst--)
      modify(1, 1, n, lst + 1, n, a[lst], tmp = Inf);
    ans[que[i].id] = query(1, 1, n, que[i].l, que[i].r);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
