#include <bits/stdc++.h>
const int INF = 2147483647;
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }
int read() {
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  int x = ch - '0';
  while (1) {
    ch = getchar();
    if (ch < '0' || ch > '9') return x;
    x = (x << 3) + (x << 1) + ch - '0';
  }
}
int bit[100005];
void add(int x, int v, int n) {
  while (x <= n) bit[x] = min(bit[x], v), x += (x & (-x));
}
int qry(int x, int n) {
  int ret = INF;
  while (x > n) ret = min(ret, bit[x]), x ^= (x & (-x));
  return ret;
}
int cmp(const void *x, const void *y) { return *(int *)y - *(int *)x; }
int a[100005], Q[300005][3], ans[300005];
struct node {
  node *ch[2];
  int id, mi, pri;
  node(int x) : id(x), mi(x) {
    ch[0] = ch[1] = NULL;
    pri = rand();
  }
  int cmp(int x) { return a[x] > a[id] ? 1 : 0; }
  void pull() {
    mi = id;
    if (ch[0]) mi = min(mi, ch[0]->mi);
    if (ch[1]) mi = min(mi, ch[1]->mi);
  }
} * root;
void rotate(node *&o, int d) {
  node *k = o->ch[d ^ 1];
  o->ch[d ^ 1] = k->ch[d], k->ch[d] = o;
  o->pull(), k->pull();
  o = k;
}
void insert(node *&o, int x) {
  if (o == NULL)
    o = new node(x);
  else {
    int d = o->cmp(x);
    insert(o->ch[d], x);
    if (o->ch[d]->pri > o->pri)
      rotate(o, d ^ 1);
    else
      o->pull();
  }
}
int getmin(int x, int y) {
  if (x > y) return INF;
  node *o = root;
  int ret = INF;
  while (o) {
    if (a[o->id] < x)
      o = o->ch[1];
    else if (a[o->id] > y)
      o = o->ch[0];
    else {
      ret = min(ret, o->id);
      node *o1 = o->ch[0];
      while (o1) {
        if (a[o1->id] < x)
          o1 = o1->ch[1];
        else {
          ret = min(ret, o1->id);
          if (o1->ch[1]) ret = min(ret, o1->ch[1]->mi);
          o1 = o1->ch[0];
        }
      }
      node *o2 = o->ch[1];
      while (o2) {
        if (a[o2->id] > y)
          o2 = o2->ch[0];
        else {
          ret = min(ret, o2->id);
          if (o2->ch[0]) ret = min(ret, o2->ch[0]->mi);
          o2 = o2->ch[1];
        }
      }
      break;
    }
  }
  return ret;
}
int main() {
  srand(514);
  int n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  int q = read();
  for (int i = 0; i < q; ++i) Q[i][0] = read(), Q[i][1] = read(), Q[i][2] = i;
  qsort(Q, q, 12, cmp);
  int last = n;
  for (int i = 0; i < q; ++i) {
    while (last > Q[i][0]) {
      bit[last] = INF;
      insert(root, last--);
      int x1 = getmin(a[last], INF);
      while (x1 <= n) {
        add(x1, a[x1] - a[last], n);
        x1 = getmin(a[last], ((a[x1] + a[last] + 1) >> 1) - 1);
      }
      int x2 = getmin(0, a[last]);
      while (x2 <= n) {
        add(x2, a[last] - a[x2], n);
        x2 = getmin(((a[x2] + a[last]) >> 1) + 1, a[last]);
      }
    }
    ans[Q[i][2]] = qry(Q[i][1], last);
  }
  for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
  return 0;
}
