#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
const int inf = 1e9 + 143;
const long long longinf = 1e18 + 143;
inline int read() {
  int x;
  scanf(" %d", &x);
  return x;
}
const int N = 1e5 + 100;
const int M = 3e5 + 100;
const int K = 350;
int n, m;
int inp[N], ord[N];
pair<int, int> a[N];
vector<pair<pair<int, int>, int>> qs[N / K + 10];
pair<int, int> smalls[N];
int answer[M];
int curBest;
struct fenwick {
  int f[N];
  void init() {
    for (int i = 0; i < N; i++) {
      f[i] = -1;
    }
  }
  void add(int x, int val) {
    ++x;
    while (x < N) {
      umax(f[x], val);
      x += x & -x;
    }
  }
  int get(int x) {
    ++x;
    int res = -1;
    while (x > 0) {
      umax(res, f[x]);
      x -= x & -x;
    }
    return res;
  }
};
fenwick fl, fr;
void activate(int at) {
  int id = ord[at];
  int lfId = fl.get(id);
  if (lfId != -1) {
    umin(curBest, inp[at] - a[lfId].first);
  }
  int rgId = fr.get(n - id - 1);
  if (rgId != -1) {
    umin(curBest, a[n - rgId - 1].first - inp[at]);
  }
  fl.add(id, id);
  fr.add(n - id - 1, n - id - 1);
}
int main() {
  n = read();
  for (int i = 0; i < n; i++) {
    inp[i] = read();
    a[i].first = inp[i];
    a[i].second = i;
  }
  m = read();
  for (int i = 0; i < m; i++) {
    int l = read() - 1;
    int r = read() - 1;
    if (l > r) {
      swap(l, r);
    }
    qs[l / K].push_back({pair<int, int>(r, l), i});
  }
  sort(a, a + n);
  for (int i = 0; i < n; i++) {
    ord[a[i].second] = i;
  }
  for (int from = 0; from < n; from += K) {
    int to = min(from + K - 1, n - 1);
    int bid = from / K;
    sort((qs[bid]).begin(), (qs[bid]).end());
    int sz = 0;
    for (int i = from; i <= to; i++) {
      smalls[sz++] = {inp[i], i};
    }
    sort(smalls, smalls + sz);
    curBest = inf;
    fl.init();
    fr.init();
    int ptr = to + 1;
    for (auto e : qs[bid]) {
      int qr = e.first.first;
      int ql = e.first.second;
      int qid = e.second;
      while (ptr <= qr) {
        activate(ptr);
        ptr++;
      }
      answer[qid] = curBest;
      int prev = -1;
      for (int i = 0; i < sz; i++) {
        int idx = smalls[i].second;
        int val = smalls[i].first;
        if (idx >= ql && idx <= qr) {
          if (prev != -1) umin(answer[qid], val - prev);
          {
            int id = ord[idx];
            int lfId = fl.get(id);
            if (lfId != -1) {
              umin(answer[qid], val - a[lfId].first);
            }
            int rgId = fr.get(n - id - 1);
            if (rgId != -1) {
              umin(answer[qid], a[n - rgId - 1].first - val);
            }
          }
          prev = val;
        }
      }
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%d\n", answer[i]);
  }
  return 0;
}
