#include <bits/stdc++.h>
using namespace std;
int n, m, a[200127], rt[200127], tot = 0, c[10000127][2], ma[10000127], U;
void change(int &p, int o, int l, int r, int x, int v) {
  p = ++tot;
  ma[p] = ma[o];
  c[p][0] = c[o][0];
  c[p][1] = c[o][1];
  if (l == r) {
    ma[p] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    change(c[p][0], c[o][0], l, mid, x, v);
  else
    change(c[p][1], c[o][1], mid + 1, r, x, v);
  ma[p] = max(ma[c[p][0]], ma[c[p][1]]);
}
int Ask(int p, int l, int r, int L, int R) {
  if (!p) return 0;
  if ((r < L) || (R < l)) return 0;
  if ((L <= l) && (r <= R)) return ma[p];
  int mid = (l + r) >> 1;
  return max(Ask(c[p][0], l, mid, L, R), Ask(c[p][1], mid + 1, r, L, R));
}
struct Point {
  int y, v;
};
vector<Point> t[200127], q[200127];
inline int Abs(int x) { return (x >= 0) ? x : (-x); }
inline void Find1(int x) {
  int p, pos = x - 1, l = a[x], r = U;
  while (true) {
    if ((l > r) || (!pos)) break;
    p = Ask(rt[pos], 0, U, l, r);
    if (!p) break;
    t[p].push_back((Point){x, Abs(a[x] - a[p])});
    if (a[x] == a[p]) break;
    pos = p - 1;
    r = (l + a[p]) >> 1;
  }
}
inline void Find2(int x) {
  int p, pos = x - 1, l = 0, r = a[x];
  while (true) {
    if ((l > r) || (!pos)) break;
    p = Ask(rt[pos], 0, U, l, r);
    if (!p) break;
    t[p].push_back((Point){x, Abs(a[x] - a[p])});
    if (a[x] == a[p]) break;
    pos = p - 1;
    l = (a[p] + r + 1) >> 1;
  }
}
int c1[200127], ans[200127 << 1];
inline void change1(int x, int v) {
  for (; x <= n; x += x & (-x)) c1[x] = min(c1[x], v);
}
inline int Ask1(int x) {
  int res = 0x3f3f3f3f;
  for (; x; x -= x & (-x)) res = min(res, c1[x]);
  return res;
}
int main() {
  scanf("%d", &n);
  int i, x, y;
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    U = max(U, a[i]);
  }
  for (i = 1; i <= n; i++) change(rt[i], rt[i - 1], 0, U, a[i], i);
  for (i = 1; i <= n; i++) {
    Find1(i);
    Find2(i);
  }
  memset(c1, 0x3f, sizeof(c1));
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    q[x].push_back((Point){y, i});
  }
  for (i = n; i >= 1; i--) {
    for (auto v : t[i]) change1(v.y, v.v);
    for (auto v : q[i]) ans[v.v] = Ask1(v.y);
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
