#include <bits/stdc++.h>
using namespace std;
struct tri {
  int a, b, c;
};
bool cmp(const tri& A, const tri& B) { return A.b < B.b; }
int min(int a, int b) {
  if (a < b) return a;
  return b;
}
int a[101010];
tri q[310101];
int ans[310100];
int best = 0;
struct Ver {
  int* a;
  int ans;
};
Ver tr[402020];
int* getNew(int cnt) { return new int[cnt]; }
void build(int cur, int l, int r) {
  tr[cur].a = getNew(r - l + 1);
  if (l == r) {
    tr[cur].a[0] = a[l];
    tr[cur].ans = 1011110000;
  } else {
    int m = (l + r) / 2;
    int dcur = cur + cur;
    build(dcur, l, m);
    build(dcur + 1, m + 1, r);
    int siz = r - l + 1;
    std::merge(tr[dcur].a, tr[dcur].a + m - l + 1, tr[dcur + 1].a,
               tr[dcur + 1].a + r - m, tr[cur].a);
    int ans = 1011110000;
    for (int i = 1; i < siz; ++i) {
      ans = min(ans, tr[cur].a[i] - tr[cur].a[i - 1]);
    }
    tr[cur].ans = ans;
  }
}
int getAns(int cur, int l, int r, int x, int y);
void update(int cur, int l, int r, int to, int x, int& d) {
  if (l == r) {
    tr[cur].ans = min(tr[cur].ans, abs(x - tr[cur].a[0]));
    d = min(tr[cur].ans, d);
  } else {
    int m = (l + r) / 2;
    int dcur = cur + cur;
    int siz = r - l + 1;
    int* it = std::lower_bound(tr[cur].a, tr[cur].a + siz, x);
    if ((it == tr[cur].a + siz || *it >= x + d) &&
        (it == tr[cur].a || *(it - 1) <= x - d)) {
      d = min(d, getAns(cur, l, r, l, to));
      return;
    }
    if (to > m) {
      update(dcur + 1, m + 1, r, to, x, d);
      update(dcur, l, m, m, x, d);
    } else {
      update(dcur, l, m, to, x, d);
    }
    tr[cur].ans = min(tr[cur].ans, min(tr[dcur].ans, tr[dcur + 1].ans));
  }
}
int getAns(int cur, int l, int r, int x, int y) {
  if (l == x && r == y) {
    return tr[cur].ans;
  } else {
    int m = (l + r) / 2;
    int dcur = cur + cur;
    if (y <= m) {
      return getAns(dcur, l, m, x, y);
    } else if (x > m) {
      return getAns(dcur + 1, m + 1, r, x, y);
    } else {
      return min(getAns(dcur, l, m, x, m),
                 getAns(dcur + 1, m + 1, r, m + 1, y));
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  int m;
  scanf("%d", &m);
  int qs = 0;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x;
    --y;
    const int K = 31;
    if (y - x <= K) {
      int ars[K + 1];
      int siz = y - x + 1;
      for (int i = x; i <= y; ++i) {
        ars[i - x] = a[i];
      }
      sort(ars, ars + siz);
      int ans = ars[1] - ars[0];
      for (int i = 2; i < siz; ++i) {
        ans = min(ans, ars[i] - ars[i - 1]);
      }
      ::ans[i] = ans;
    } else {
      q[qs++] = {x, y, i};
    }
  }
  sort(q, q + qs, cmp);
  int curr = 0;
  build(1, 0, n - 1);
  for (int i = 0; i < qs; i++) {
    tri curq = q[i];
    int l = curq.a;
    int r = curq.b;
    int idx = curq.c;
    while (curr < r) {
      ++curr;
      int d = 1011110000;
      update(1, 0, n - 1, curr - 1, a[curr], d);
    }
    ans[idx] = getAns(1, 0, n - 1, l, r);
  }
  for (int i = 0; i < m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
