#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T& num) {
  bool start = false, neg = false;
  char c;
  num = 0;
  while ((c = getchar()) != EOF) {
    if (c == '-')
      start = neg = true;
    else if (c >= '0' && c <= '9') {
      start = true;
      num = num * 10 + c - '0';
    } else if (start)
      break;
  }
  if (neg) num = -num;
}
const int maxn = (int)(3e5) + 5;
const int INF = (int)(1e9) + 100;
int a[maxn];
int res[maxn];
int mi[maxn << 2];
set<int> s[maxn << 2];
int n;
struct node {
  int l, r, id;
} p[maxn];
inline bool operator<(node a, node b) { return a.r < b.r; }
void build(int x, int l, int r) {
  mi[x] = INF;
  for (int i = (l); i <= (r); i++) s[x].insert(a[i]);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}
int qm(int x, int l, int r, int s, int t) {
  if (s <= l && r <= t) return mi[x];
  int mid = (l + r) >> 1, res = INF;
  if (s <= mid) res = min(res, qm(x << 1, l, mid, s, t));
  if (mid < t) res = min(res, qm(x << 1 | 1, mid + 1, r, s, t));
  return res;
}
int now;
inline int iabs(int x) { return x >= 0 ? x : -x; }
void modify(int x, int l, int r, int ps, int v) {
  if (l == r) {
    now = min(now, iabs(a[l] - v));
    mi[x] = min(mi[x], now);
    return;
  }
  if (r <= ps) {
    set<int>::iterator it = s[x].lower_bound(v);
    if (it == s[x].end() || (*it) - v >= 2 * now) {
      if (it == s[x].begin() || v - (*(--it)) >= 2 * now) {
        now = min(now, qm(1, 1, n, l, ps));
        return;
      }
    }
  }
  int mid = (l + r) >> 1;
  if (ps > mid) modify(x << 1 | 1, mid + 1, r, ps, v);
  modify(x << 1, l, mid, ps, v);
  mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
}
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) read(a[i]);
  int m;
  read(m);
  for (int i = (1); i <= (m); i++) {
    read(p[i].l);
    read(p[i].r);
    p[i].id = i;
  }
  sort(p + 1, p + m + 1);
  build(1, 1, n);
  int ps = 2;
  for (int i = (1); i <= (m); i++) {
    while (ps <= p[i].r) {
      now = INF;
      modify(1, 1, n, ps - 1, a[ps]);
      ps++;
    }
    res[p[i].id] = qm(1, 1, n, p[i].l, p[i].r);
  }
  for (int i = (1); i <= (m); i++) printf("%d\n", res[i]);
  return 0;
}
