#include <bits/stdc++.h>
using namespace std;
const int ST_MAX = (1 << 18);
const int INF = 1e9 + 7;
template <class T>
class ST {
  T x[ST_MAX * 2];
  T eval(T a, T b) { return max(a, b); }
  void ren(int a) {
    x[a] = eval(x[2 * a], x[2 * a + 1]);
    if (a > 0) ren(a / 2);
  }
  T read_ST(int a, int b, int e, int s, int f) {
    if (e <= s || f <= b) return -1;
    if (s <= b && e <= f) return x[a];
    return eval(read_ST(2 * a, b, (b + e) / 2, s, f),
                read_ST(2 * a + 1, (b + e) / 2, e, s, f));
  }

 public:
  ST() { fill(x, x + ST_MAX * 2, -1); }
  void put(int a, T b) {
    x[a + ST_MAX] = b;
    ren((a + ST_MAX) / 2);
  }
  T get(int s, int f) {
    if (s >= f) return -1;
    return read_ST(1, 0, ST_MAX, s, f);
  }
};
template <class T, class U>
class STL {
  T x[ST_MAX * 2];
  U lazy[ST_MAX * 2];
  T eval(T a, T b) { return min(a, b); }
  U syn(U a, U b) { return min(a, b); }
  void work(int a) {
    if (a < ST_MAX) {
      lazy[a * 2] = syn(lazy[a], lazy[a * 2]);
      lazy[a * 2 + 1] = syn(lazy[a], lazy[a * 2 + 1]);
    }
    x[a] = min(x[a], lazy[a]);
    lazy[a] = INF;
  }
  void ren(int a, int b, int e, int s, int f, U z) {
    if (e <= s || f <= b) {
      work(a);
      return;
    }
    if (s <= b && e <= f) {
      lazy[a] = syn(lazy[a], z);
      work(a);
      return;
    }
    work(a);
    ren(2 * a, b, (b + e) / 2, s, f, z);
    ren(2 * a + 1, (b + e) / 2, e, s, f, z);
    x[a] = eval(x[a * 2], x[a * 2 + 1]);
  }
  T read_ST(int a, int b, int e, int s, int f) {
    work(a);
    if (e <= s || f <= b) return INF;
    if (s <= b && e <= f) return x[a];
    return eval(read_ST(2 * a, b, (b + e) / 2, s, f),
                read_ST(2 * a + 1, (b + e) / 2, e, s, f));
  }

 public:
  STL() {
    fill(x, x + ST_MAX * 2, INF);
    fill(lazy, lazy + ST_MAX * 2, INF);
  }
  void put(int s, int f, U b) { ren(1, 0, ST_MAX, s, f, b); }
  T get(int s, int f) { return read_ST(1, 0, ST_MAX, s, f); }
};
ST<int> st;
STL<int, int> solve;
int n, m;
int a[100010], d[100010];
int l[300010], r[300010];
int q[300010], c[100010];
int ans[300010];
bool comp_a(const int x, const int y) {
  if (a[x] == a[y]) return x < y;
  return a[x] < a[y];
}
bool comp(const int x, const int y) { return r[x] < r[y]; }
int BS(int x, int y, int p) {
  if (y - x < 2) return y;
  int z = (x + y) / 2;
  return a[c[z]] < p ? BS(z, y, p) : BS(x, z, p);
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(0); i < (int)(n); ++i) {
    scanf("%d", a + i);
    c[i] = i;
  }
  scanf("%d", &m);
  for (int i = (int)(0); i < (int)(m); ++i) {
    scanf("%d%d", l + i, r + i);
    --l[i];
    --r[i];
    q[i] = i;
  }
  sort(c, c + n, comp_a);
  sort(q, q + m, comp);
  for (int i = (int)(0); i < (int)(n); ++i) {
    d[c[i]] = i;
  }
  a[n] = INF;
  c[n] = n;
  d[n] = n;
  int z = 0;
  for (int i = (int)(0); i < (int)(n); ++i) {
    int x = st.get(d[i] + 1, n);
    while (x >= 0) {
      solve.put(0, x + 1, a[x] - a[i]);
      x = st.get(d[i] + 1, BS(-1, n, (a[i] + a[x] + 1) / 2));
    }
    x = st.get(0, d[i]);
    while (x >= 0) {
      solve.put(0, x + 1, a[i] - a[x]);
      x = st.get(BS(-1, n, (a[i] + a[x] + 2) / 2), d[i]);
    }
    while (z < m && r[q[z]] == i) {
      ans[q[z]] = solve.get(l[q[z]], r[q[z]]);
      ++z;
    }
    st.put(d[i], i);
  }
  for (int i = (int)(0); i < (int)(m); ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
