#include <bits/stdc++.h>
using namespace std;
namespace IO {
char ibuf[(1 << 21) + 1], obuf[(1 << 21) + 1], st[20], *iS, *iT,
    *oS = obuf, *oT = obuf + (1 << 21);
char Get() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, (1 << 21) + 1, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
void Flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
void Put(char x) {
  *oS++ = x;
  if (oS == oT) Flush();
}
int read() {
  int x = 0;
  char ch = Get();
  while (ch > 57 || ch < 48) ch = Get();
  while (ch >= 48 && ch <= 57) x = x * 10 + (ch ^ 48), ch = Get();
  return x;
}
void write(int x) {
  int top = 0;
  if (!x) Put('0');
  while (x) st[++top] = (x % 10) + 48, x /= 10;
  while (top) Put(st[top--]);
  Put('\n');
}
}  // namespace IO
using namespace IO;
int min(int a, int b) { return a < b ? a : b; }
const int N = 200007, M = 300007, INF = 1e9;
int a[N], ans[N << 2], Ans[N << 2], n, m, mn;
vector<int> vec[N << 2];
struct node {
  int l, r, id;
} q[M];
int operator<(node a, node b) { return a.r < b.r; }
void build(int p, int l, int r) {
  for (int i = l; i <= r; ++i) vec[p].push_back(a[i]);
  sort(vec[p].begin(), vec[p].end()), ans[p] = INF;
  if (l == r) return;
  build(p << 1, l, ((l + r) >> 1)), build(p << 1 | 1, ((l + r) >> 1) + 1, r);
}
int query(int p, int l, int r, int L, int R) {
  if (L == l && r == R) return ans[p];
  return R <= ((l + r) >> 1)
             ? query(p << 1, l, ((l + r) >> 1), L, R)
             : (L > ((l + r) >> 1)
                    ? query(p << 1 | 1, ((l + r) >> 1) + 1, r, L, R)
                    : min(query(p << 1, l, ((l + r) >> 1), L, ((l + r) >> 1)),
                          query(p << 1 | 1, ((l + r) >> 1) + 1, r,
                                ((l + r) >> 1) + 1, R)));
}
void update(int p, int l, int r, int f, int x) {
  if (r <= f) {
    vector<int>::iterator it = upper_bound(vec[p].begin(), vec[p].end(), x);
    if (it != vec[p].end()) ans[p] = min(ans[p], *it - x);
    if (it != vec[p].begin()) ans[p] = min(ans[p], x - *(it - 1));
    if (mn <= ans[p]) return;
    if (l == r) return (void)(mn = min(mn, ans[p]));
  }
  if (f > ((l + r) >> 1)) update(p << 1 | 1, ((l + r) >> 1) + 1, r, f, x);
  update(p << 1, l, ((l + r) >> 1), f, x),
      ans[p] = min(ans[p], min(ans[p << 1], ans[p << 1 | 1])),
      mn = min(mn, ans[p]);
}
int main() {
  int i, j;
  n = read();
  for (i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n), m = read();
  for (i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].id = i;
  sort(q + 1, q + m + 1);
  for (j = 1, i = 2; i <= n; ++i) {
    mn = INF, update(1, 1, n, i - 1, a[i]);
    for (; j <= m && q[j].r <= i; ++j) Ans[q[j].id] = query(1, 1, n, q[j].l, i);
  }
  for (i = 1; i <= m; ++i) write(Ans[i]);
  return Flush(), 0;
}
