#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline long long llread() {
  char ch = getchar();
  long long x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, a[300010], mp[300010], BS;
pair<int, int> b[300010];
int mxnum;
inline void lisanhua() {
  for (int i = (1); i <= (n); i++) b[i] = make_pair(a[i], i);
  sort(b + 1, b + n + 1);
  b[0].first = -1;
  int tot = 0;
  for (int i = (1); i <= (n); i++) {
    tot++;
    mp[tot] = b[i].first;
    a[b[i].second] = tot;
  }
  mxnum = tot;
}
struct que {
  int l, r, id;
  inline bool operator<(const que& rhs) const { return r > rhs.r; }
};
vector<que> Group[333];
int f[333][300010 / 3 + 10];
inline int dp(int len, int r) {
  if (f[len][r]) return f[len][r];
  if (len == 2) return f[len][r] = abs(mp[a[r - 1]] - mp[a[r]]);
  return f[len][r] = min(min(dp(len - 1, r), dp(len - 1, r - 1)),
                         abs(mp[a[r]] - mp[a[r - len + 1]]));
}
int Pre[300010], Next[300010];
inline int Cancel(int x) {
  int ret = 1047483647;
  Pre[Next[x]] = x;
  Next[Pre[x]] = x;
  if (Pre[x] > 0) ret = min(ret, abs(mp[Pre[x]] - mp[x]));
  if (Next[x] <= mxnum) ret = min(ret, abs(mp[Next[x]] - mp[x]));
  return ret;
}
inline void Delete(int x) {
  Pre[Next[x]] = Pre[x];
  Next[Pre[x]] = Next[x];
}
inline void init() {
  for (int i = (1); i <= (mxnum); i++) Pre[i] = i - 1, Next[i] = i + 1;
  Next[0] = 1;
  Pre[mxnum + 1] = mxnum;
}
int ans[300010], mn[300010];
int main() {
  n = read();
  for (int i = (1); i <= (n); i++) a[i] = read();
  lisanhua();
  int m = read();
  BS = sqrt(n);
  BS = 330;
  for (int i = (1); i <= (n); i++) f[1][i] = 1047483647;
  for (int i = (2); i <= (330); i++) {
    for (int j = (i); j <= (n); j++) {
      f[i][j] = min(min(f[i - 1][j], f[i - 1][j - 1]),
                    abs(mp[a[j]] - mp[a[j - i + 1]]));
    }
  }
  for (int i = (1); i <= (m); i++) {
    int l = read(), r = read();
    if (r - l + 1 <= BS) {
      if (l == r)
        ans[i] = 0;
      else
        ans[i] = f[r - l + 1][r];
    } else
      Group[l / BS].push_back((que){l, r, i});
  }
  int Gsize = n / BS + 1;
  for (int i = (0); i < (Gsize); i++) {
    if (Group[i].empty()) continue;
    int p = i * BS, q = i * BS + BS - 1;
    if (p == 0) p = 1;
    if (q > n) q = n;
    init();
    for (int j = (1); j <= (q - 1); j++) Delete(a[j]);
    for (int j = (n); j >= (q + 1); j--) Delete(a[j]);
    mn[q] = 1047483647;
    for (int j = (q + 1); j <= (n); j++) mn[j] = min(mn[j - 1], Cancel(a[j]));
    for (int j = (q - 1); j >= (p); j--) Cancel(a[j]);
    sort(Group[i].begin(), Group[i].end());
    int pos = n;
    for (int j = (0); j < (Group[i].size()); j++) {
      int l = Group[i][j].l, r = Group[i][j].r;
      while (pos > r) Delete(a[pos]), pos--;
      int res = mn[r];
      for (int k = (p); k <= (q - 1); k++) Delete(a[k]);
      for (int k = (q - 1); k >= (l); k--) res = min(res, Cancel(a[k]));
      for (int k = (l - 1); k >= (p); k--) Cancel(a[k]);
      ans[Group[i][j].id] = res;
    }
  }
  for (int i = (1); i <= (m); i++) printf("%d\n", ans[i]);
  return 0;
}
