#include <bits/stdc++.h>
using namespace std;
int read() {
  char c = getchar();
  long long x = 1, s = 0;
  while (c < '0' || c > '9') {
    if (c == '-') x = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * x;
}
const int N = 3e5 + 5;
int n, m, a[N], l, r, ans[N], minn[N * 4];
vector<int> s[N];
vector<pair<int, int> > q[N];
void build(int u, int l, int r) {
  for (int i = l; i <= r; i++) s[u].push_back(a[i]);
  sort(s[u].begin(), s[u].end());
  minn[u] = 2e9 + 7;
  if (l == r) return;
  build((u << 1), l, ((l + r) >> 1));
  build((u << 1 | 1), ((l + r) >> 1) + 1, r);
}
int maxx = 0, ne;
void modify(int u, int l, int r, int x) {
  int tmp = 2e9 + 7;
  int pre = upper_bound(s[u].begin(), s[u].end(), ne) - s[u].begin() - 1;
  int prv = upper_bound(s[u].begin(), s[u].end(), ne) - s[u].begin();
  if (pre >= 0) tmp = min(tmp, abs(ne - s[u][pre]));
  if (prv != s[u].size()) tmp = min(tmp, abs(ne - s[u][prv]));
  if (tmp >= maxx) return;
  if (l == r) {
    minn[u] = min(minn[u], abs(a[l] - ne));
    maxx = min(maxx, minn[u]);
    return;
  }
  if (x > ((l + r) >> 1)) modify((u << 1 | 1), ((l + r) >> 1) + 1, r, x);
  maxx = min(maxx, minn[(u << 1 | 1)]);
  modify((u << 1), l, ((l + r) >> 1), x);
  minn[u] = min(minn[(u << 1)], minn[(u << 1 | 1)]);
}
int query(int u, int l, int r, int L, int R) {
  if (L <= l and R >= r) {
    return minn[u];
  }
  int maa = 2e9 + 7;
  if (L <= ((l + r) >> 1))
    maa = min(maa, query((u << 1), l, ((l + r) >> 1), L, R));
  if (R > ((l + r) >> 1))
    maa = min(maa, query((u << 1 | 1), ((l + r) >> 1) + 1, r, L, R));
  return maa;
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  build(1, 1, n);
  m = read();
  for (int i = 1; i <= m; i++) {
    l = read();
    r = read();
    q[r].push_back(make_pair(l, i));
  }
  for (int i = 2; i <= n; i++) {
    maxx = 2e9 + 7;
    ne = a[i];
    modify(1, 1, n, i - 1);
    for (int k = 0; k < q[i].size(); k++) {
      ans[q[i][k].second] = query(1, 1, n, q[i][k].first, i - 1);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
