#include <bits/stdc++.h>
using namespace std;
int getint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}
int n;
int v[112345], pos[112345], a[112345];
struct node {
  int l, r;
  int mx;
} tr[112345 << 2];
void pushup(int i) { tr[i].mx = max(tr[i << 1].mx, tr[i << 1 | 1].mx); }
void build(int i, int l, int r) {
  tr[i].l = l;
  tr[i].r = r;
  if (l == r) {
    tr[i].mx = -1;
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  pushup(i);
}
int query(int i, int fl, int fr) {
  int l = tr[i].l, r = tr[i].r;
  if (r < fl || fr < l) return -1;
  if (fl <= l && r <= fr) return tr[i].mx;
  return max(query(i << 1, fl, fr), query(i << 1 | 1, fl, fr));
}
void modify(int i, int j, int x) {
  int l = tr[i].l, r = tr[i].r;
  if (j < l || j > r) return;
  if (l == r) {
    tr[i].mx = x;
    return;
  }
  modify(i << 1, j, x);
  modify(i << 1 | 1, j, x);
  pushup(i);
}
int c[112345];
void add(int i, int x) {
  for (; i < 112345; i += i & (-i)) c[i] = min(c[i], x);
}
int qu(int i) {
  int res = 0x3f3f3f3f;
  for (; i; i -= i & (-i)) res = min(res, c[i]);
  return res;
}
struct req {
  int l, id;
  req() {}
  req(int _, int __) {
    l = _;
    id = __;
  }
};
vector<req> q[112345 * 3];
int answer[112345 * 3];
vector<int> aa[112345];
int st[112345], top = 0;
bool vis[112345];
int main() {
  n = getint();
  for (int i = 1; i <= n; i++) a[i] = v[i] = getint();
  sort(v + 1, v + 1 + n);
  for (int i = 1; i <= n; i++)
    pos[i] = lower_bound(v + 1, v + 1 + n, a[i]) - v, aa[pos[i]].push_back(i);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < aa[i].size(); j++) pos[aa[i][j]] += j;
  }
  build(1, 1, n);
  int t = getint();
  for (int i = 1; i <= t; i++) {
    int l = getint(), r = getint();
    q[r].push_back(req(l, i));
  }
  for (int i = 1; i <= n; i++) c[i] = 0x3f3f3f3f;
  for (int i = 1; i <= n; i++) {
    int l = pos[i] + 1, r = n;
    while (l <= r) {
      int j = query(1, l, r);
      if (j == -1) break;
      add(n - j + 1, a[j] - a[i]);
      if (a[j] == a[i]) break;
      int y = a[i] + (a[j] - a[i]) / 2;
      r = upper_bound(v + 1, v + 1 + n, y) - v - 1;
    }
    l = 1, r = pos[i] - 1;
    while (l <= r) {
      int j = query(1, l, r);
      if (j == -1) break;
      add(n - j + 1, a[i] - a[j]);
      if (a[j] == a[i]) break;
      int y = a[i] - (a[i] - a[j]) / 2;
      l = lower_bound(v + 1, v + 1 + n, y) - v;
    }
    for (int j = 0; j < q[i].size(); j++) {
      answer[q[i][j].id] = qu(n - q[i][j].l + 1);
    }
    modify(1, pos[i], i);
  }
  for (int i = 1; i <= t; i++) cout << answer[i] << endl;
  return 0;
}
