#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int maxm = 300010;
const int inf = (1 << 30);
struct Node {
  set<int> T;
  int num;
} node[maxn << 2];
pair<pair<int, int>, int> qq[maxm];
int n, a[maxn], m, ans[maxm];
void build(int left, int right, int rt) {
  node[rt].num = inf;
  for (int i = left; i <= right; i++) node[rt].T.insert(a[i]);
  if (left == right) return;
  int mid = left + right >> 1;
  build(left, mid, rt << 1);
  build(mid + 1, right, rt << 1 | 1);
}
int query(int left, int right, int L, int R, int rt) {
  if (left > R || right < L) return inf;
  if (L <= left && right <= R) return node[rt].num;
  int mid = left + right >> 1;
  return min(query(left, mid, L, R, rt << 1),
             query(mid + 1, right, L, R, rt << 1 | 1));
}
void update(int left, int right, int L, int R, int x, int &mi, int rt) {
  if (left > R || right < L) return;
  if (left == right) {
    node[rt].num = min(node[rt].num, abs(x - a[left]));
    mi = min(mi, node[rt].num);
    return;
  }
  auto it = node[rt].T.lower_bound(x);
  if ((it == node[rt].T.end() || (*it - x) >= mi) &&
      (it == node[rt].T.begin() || (x - *(--it) >= mi))) {
    mi = min(mi, query(left, right, L, R, rt));
    return;
  }
  int mid = left + right >> 1;
  update(left, mid, L, R, x, mi, rt << 1);
  update(mid + 1, right, L, R, x, mi, rt << 1 | 1);
  node[rt].num = min(node[rt << 1].num, node[rt << 1 | 1].num);
}
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", &qq[i].first.first, &qq[i].first.second);
    qq[i].second = i;
  }
  sort(qq + 1, qq + m + 1);
  build(1, n, 1);
  for (int i = m, left = n; i; i--) {
    for (; left >= qq[i].first.first; left--) {
      int minnum = inf;
      update(1, n, left + 1, n, a[left], minnum, 1);
    }
    ans[qq[i].second] = query(1, n, qq[i].first.first, qq[i].first.second, 1);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
