#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 3e5 + 5;
const int INF = 2e9 + 5;
struct edge {
  int to, id, next;
} G[maxm];
int head[maxn], tot, a[maxn], bit[maxn], ans[maxm], b[maxn], node[maxn << 2];
void init(int n) {
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= n; ++i) bit[i] = INF;
  tot = 0;
}
void addedge(int u, int v, int id) {
  G[tot].to = v;
  G[tot].id = id;
  G[tot].next = head[u];
  head[u] = tot++;
}
void build(int rt, int l, int r) {
  node[rt] = maxn;
  if (l == r) return;
  int m = (l + r) >> 1;
  build(rt << 1, l, m);
  build(rt << 1 | 1, m + 1, r);
}
void update1(int rt, int l, int r, int p, int v) {
  node[rt] = min(node[rt], v);
  if (l == r) return;
  int m = (l + r) >> 1;
  if (p <= m)
    update1(rt << 1, l, m, p, v);
  else
    update1(rt << 1 | 1, m + 1, r, p, v);
}
int query1(int rt, int l, int r, int x, int y) {
  if (x <= l && r <= y) return node[rt];
  int m = (l + r) >> 1, ret = maxn;
  if (x <= m) ret = min(ret, query1(rt << 1, l, m, x, y));
  if (m < y) ret = min(ret, query1(rt << 1 | 1, m + 1, r, x, y));
  return ret;
}
void update2(int i, int v, int n) {
  while (i <= n) {
    bit[i] = min(bit[i], v);
    i += i & -i;
  }
}
int query2(int i) {
  int ret = INF;
  while (i) {
    ret = min(bit[i], ret);
    i -= i & -i;
  }
  return ret;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  int cnt = unique(b + 1, b + n + 1) - b - 1;
  build(1, 1, cnt);
  int q;
  scanf("%d", &q);
  init(n);
  for (int i = 1; i <= q; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    addedge(l, r, i);
  }
  for (int i = n; i > 0; --i) {
    int x = a[i], y = INF;
    int l = lower_bound(b + 1, b + cnt + 1, x) - b;
    while (y > x) {
      int r = upper_bound(b + 1, b + cnt + 1, x + (y - x - 1) / 2) - b - 1;
      int p = query1(1, 1, cnt, l, r);
      if (p >= maxn) break;
      update2(p, a[p] - x, n);
      y = a[p];
    }
    y = -INF;
    while (y < x) {
      int r = lower_bound(b + 1, b + cnt + 1, (x + y) / 2 + 1) - b;
      int p = query1(1, 1, cnt, r, l);
      if (p >= maxn) break;
      update2(p, x - a[p], n);
      y = a[p];
    }
    for (int j = head[i]; ~j; j = G[j].next) ans[G[j].id] = query2(G[j].to);
    update1(1, 1, cnt, l, i);
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  return 0;
}
