#include <bits/stdc++.h>
using namespace std;
namespace IO {
const unsigned int Buffsize = 1 << 15, Output = 1 << 23;
static char Ch_[Buffsize], *S_ = Ch_, *T_ = Ch_;
static char Out[Output], *nowps = Out;
inline void flush() {
  fwrite(Out, 1, nowps - Out, stdout);
  nowps = Out;
}
template <class T>
inline bool chkmax(T &_, T __) {
  return _ < __ ? _ = __, 1 : 0;
}
template <class T>
inline bool chkmin(T &_, T __) {
  return _ > __ ? _ = __, 1 : 0;
}
template <class T>
inline T read(T &_) {
  _ = 0;
  static char __;
  T ___ = 1;
  for (__ = ((S_ == T_) && (T_ = (S_ = Ch_) + fread(Ch_, 1, Buffsize, stdin),
                           S_ == T_)
                 ? 0
                 : *S_++);
       !isdigit(__);
       __ = ((S_ == T_) && (T_ = (S_ = Ch_) + fread(Ch_, 1, Buffsize, stdin),
                           S_ == T_)
                 ? 0
                 : *S_++))
    if (__ == '-') ___ = -1;
  for (; isdigit(__);
       __ = ((S_ == T_) && (T_ = (S_ = Ch_) + fread(Ch_, 1, Buffsize, stdin),
                           S_ == T_)
                 ? 0
                 : *S_++))
    _ = (_ << 3) + (_ << 1) + (__ ^ 48);
  return _ *= ___;
}
template <class T>
inline void write(T _, char __ = '\n') {
  if (!_) *nowps++ = ('0');
  if (_ < 0) *nowps++ = ('-'), _ = -_;
  static unsigned int sta[111], tp;
  for (tp = 0; _; _ /= 10) sta[++tp] = _ % 10;
  for (; tp; *nowps++ = (sta[tp--] ^ 48))
    ;
  *nowps++ = (__);
}
}  // namespace IO
inline void proStatus() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>());
}
using namespace IO;
const int N = 1e5 + 10;
const int M = 3e5 + 10;
vector<pair<int, int> > Q[N];
int n, q, root[N], a[N], ans[M];
struct Fenwick_Tree {
  int S[N], res;
  Fenwick_Tree() { memset(S, (0x3f3f3f3f), sizeof(S)); }
  void update(int first, int second) {
    first = n - first + 1;
    for (; first < N; first += first & -first) chkmin(S[first], second);
  }
  int query(int first) {
    first = n - first + 1;
    for (res = (0x3f3f3f3f); first; first -= first & -first)
      chkmin(res, S[first]);
    return res;
  }
} T1;
struct Chairman_Tree {
  int cnt;
  struct node {
    int ch[2], pos;
  } T[N * 200];
  void update(int &first, int pre, int l, int r, int pos, int val) {
    T[first = ++cnt] = T[pre], chkmax(T[first].pos, pos);
    if (l ^ r) {
      if (val <= ((l + r) >> 1))
        update((T[first].ch[0]), (T[pre].ch[0]), l, ((l + r) >> 1), pos, val);
      else
        update((T[first].ch[1]), (T[pre].ch[1]), ((l + r) >> 1) + 1, r, pos,
               val);
    }
  }
  int query(int first, int l, int r, int mn, int mx) {
    if (mn > mx || !first) return 0;
    if (mn <= l && r <= mx) return T[first].pos;
    if (mx <= ((l + r) >> 1))
      return query((T[first].ch[0]), l, ((l + r) >> 1), mn, mx);
    if (mn > ((l + r) >> 1))
      return query((T[first].ch[1]), ((l + r) >> 1) + 1, r, mn, mx);
    return max(
        query((T[first].ch[0]), l, ((l + r) >> 1), mn, ((l + r) >> 1)),
        query((T[first].ch[1]), ((l + r) >> 1) + 1, r, ((l + r) >> 1), mx));
  }
} T2;
int main() {
  int first, second;
  read(n);
  for (int i = 1; i <= n; ++i)
    T2.update(root[i], root[i - 1], 0, 1e9, i, read(a[i]));
  read(q);
  for (int i = 1; i <= q; ++i)
    read(first), Q[read(second)].push_back(make_pair(first, i));
  for (int r = 1, pos, lim; r <= n; ++r) {
    pos = r, lim = (0x3f3f3f3f);
    while (pos = T2.query(root[pos - 1], 0, 1e9, a[r], lim))
      T1.update(pos, a[pos] - a[r]),
          lim = (a[pos] + a[r]) / 2 - (((a[r] + a[pos] + 1) & 1));
    pos = r, lim = -(0x3f3f3f3f);
    while (pos = T2.query(root[pos - 1], 0, 1e9, lim, a[r]))
      T1.update(pos, a[r] - a[pos]),
          lim = (a[pos] + a[r]) / 2 + (((a[r] + a[pos] + 1) & 1));
    for (auto v : Q[r]) ans[v.second] = T1.query(v.first);
  }
  for (int i = 1; i <= q; ++i) write(ans[i]);
  return flush(), 0;
}
