#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
int arr[MAXN];
int gre[MAXN];
int les[MAXN];
vector<pair<int, int> > cons[MAXN];
int mini[4 * MAXN];
vector<int> qu[MAXN];
void build(int start, int end, int node) {
  if (start == end) {
    mini[node] = 1e9;
    return;
  }
  build(start, (start + end) / 2, 2 * node);
  build((start + end) / 2 + 1, end, 2 * node + 1);
  mini[node] = 1e9;
}
void update(int start, int end, int i, int j, int node) {
  if (start > i || end < i) return;
  if (start == end) {
    mini[node] = min(mini[node], j);
    return;
  }
  update(start, (start + end) / 2, i, j, 2 * node);
  update((start + end) / 2 + 1, end, i, j, 2 * node + 1);
  mini[node] = min(mini[2 * node], mini[2 * node + 1]);
}
int query(int start, int end, int i, int j, int node) {
  if (start > j || end < i) return 1e9;
  if (start >= i && end <= j) return mini[node];
  int le = query(start, (start + end) / 2, i, j, 2 * node);
  int re = query((start + end) / 2 + 1, end, i, j, 2 * node + 1);
  return min(le, re);
}
int main() {
  scanf("%d", &n);
  build(1, n, 1);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
  vector<int> uni;
  for (int i = 1; i <= n; i++) uni.push_back(arr[i]);
  sort(uni.begin(), uni.end());
  auto az = unique(uni.begin(), uni.end());
  uni.erase(az, uni.end());
  vector<pair<int, int> > st;
  for (int i = n; i >= 1; i--) {
    while (st.size() && st.back().first < arr[i]) st.pop_back();
    if (!st.size())
      gre[i] = -1;
    else
      gre[i] = st.back().second;
    st.push_back(pair<int, int>(arr[i], i));
  }
  st.clear();
  for (int i = n; i >= 1; i--) {
    while (st.size() && st.back().first > arr[i]) st.pop_back();
    if (!st.size())
      les[i] = -1;
    else
      les[i] = st.back().second;
    st.push_back(pair<int, int>(arr[i], i));
  }
  for (int i = n; i >= 1; i--) {
    int pos = lower_bound(uni.begin(), uni.end(), arr[i]) - uni.begin() + 1;
    if (gre[i] != -1) {
      int lo = arr[i], hi = arr[gre[i]];
      cons[i].push_back(pair<int, int>(gre[i], hi - lo));
      if (lo != hi) {
        while (hi >= lo) {
          int mi = (hi + lo) / 2;
          int pos2 = upper_bound(uni.begin(), uni.end(), mi) - uni.begin() + 1;
          pos2--;
          int miz = query(1, uni.size(), pos, pos2, 1);
          if (miz == 1e9) break;
          cons[i].push_back(pair<int, int>(miz, arr[miz] - lo));
          if (hi == lo) break;
          hi = mi;
        }
      }
    }
    if (les[i] != -1) {
      int lo = arr[i], hi = arr[les[i]];
      cons[i].push_back(pair<int, int>(les[i], lo - hi));
      if (lo != hi) {
        while (hi <= lo) {
          int mi = (hi + lo + 1) / 2;
          int pos2 = lower_bound(uni.begin(), uni.end(), mi) - uni.begin() + 1;
          int miz = query(1, uni.size(), pos2, pos, 1);
          if (miz == 1e9) break;
          cons[i].push_back(pair<int, int>(miz, lo - arr[miz]));
          if (hi == lo) break;
          hi = mi;
        }
      }
    }
    update(1, uni.size(), pos, i, 1);
  }
  int q;
  scanf("%d", &q);
  vector<pair<int, int> > qz;
  map<pair<int, int>, int> ans;
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    qz.push_back(pair<int, int>(l, r));
    qu[l].push_back(r);
  }
  build(1, n, 1);
  for (int i = n; i >= 1; i--) {
    for (pair<int, int> j : cons[i]) update(1, n, j.first, j.second, 1);
    for (int j : qu[i]) {
      ans[pair<int, int>(i, j)] = query(1, n, i, j, 1);
    }
  }
  for (pair<int, int> i : qz) printf("%d\n", ans[i]);
  return 0;
}
