#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, c = getchar(), f = 0;
  for (; c > '9' || c < '0'; f = c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 1) + (x << 3) + c - '0', c = getchar())
    ;
  return f ? -x : x;
}
inline void write(int x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 400000 + 10;
int n, m, L, R, V, a[N], t[N * 4], cnt[2];
void build(int o, int l, int r) {
  if (l == r) {
    t[o] = a[l];
    return;
  }
  build(o << 1, l, ((l + r) >> 1));
  build(o << 1 | 1, ((l + r) >> 1) + 1, r);
  t[o] = min(t[o << 1], t[o << 1 | 1]);
}
int query(int o, int l, int r) {
  if (L <= l && R >= r) return t[o];
  int res = 1e9;
  if (L <= ((l + r) >> 1)) res = query(o << 1, l, ((l + r) >> 1));
  if (R > ((l + r) >> 1))
    res = min(query(o << 1 | 1, ((l + r) >> 1) + 1, r), res);
  return res;
}
void modify(int o, int l, int r) {
  if (l == r) {
    t[o] = V;
    return;
  }
  if (L <= ((l + r) >> 1))
    modify(o << 1, l, ((l + r) >> 1));
  else
    modify(o << 1 | 1, ((l + r) >> 1) + 1, r);
  t[o] = min(t[o << 1], t[o << 1 | 1]);
}
struct node {
  int r1, c1, r2, c2, id, mn;
  bool operator<(const node &B) const { return r2 < B.r2; }
} q[2][N];
int ans[N], s[N];
int dicl(int x) {
  int res = 0;
  for (int l = 1, r = *s; l <= r;)
    if (s[((l + r) >> 1)] < x)
      res = ((l + r) >> 1), l = ((l + r) >> 1) + 1;
    else
      r = ((l + r) >> 1) - 1;
  return res + 1;
}
int dicp(int l, int x) {
  int res = *s + 1, tmp = l;
  for (int r = *s; l <= r;)
    if (a[s[((l + r) >> 1)]] >= x)
      res = ((l + r) >> 1), r = ((l + r) >> 1) - 1;
    else
      l = ((l + r) >> 1) + 1;
  return max(res - 1, tmp);
}
int dicr(int x) {
  int res = *s + 1;
  for (int l = 1, r = *s; l <= r;)
    if (s[((l + r) >> 1)] > x)
      res = ((l + r) >> 1), r = ((l + r) >> 1) - 1;
    else
      l = ((l + r) >> 1) + 1;
  return res - 1;
}
int dicr_(int x) {
  int res = 0;
  for (int l = 1, r = *s; l <= r;)
    if (s[((l + r) >> 1)] > x)
      res = ((l + r) >> 1), l = ((l + r) >> 1) + 1;
    else
      r = ((l + r) >> 1) - 1;
  return res + 1;
}
int dic1(int l, int r, int x) {
  int res = r + 1;
  for (; l <= r;)
    if (a[s[((l + r) >> 1)]] > x)
      res = ((l + r) >> 1), r = ((l + r) >> 1) - 1;
    else
      l = ((l + r) >> 1) + 1;
  return res - 1;
}
void work(int ID) {
  *s = 0;
  memset(t, 60, sizeof t);
  for (int i = 1, pre = 0; i <= cnt[ID]; i++) {
    int r1 = q[ID][i].r1, c1 = q[ID][i].c1, r2 = q[ID][i].r2, c2 = q[ID][i].c2,
        id = q[ID][i].id, mn = q[ID][i].mn;
    ans[id] = min(abs(min(c1, mn) - c2), 1 + c2);
    if (pre < r2) {
      for (int j = pre + 1, _y = r2; j <= _y; j++) {
        for (; *s > 0 && a[s[*s]] >= a[j]; --*s)
          L = s[*s], V = 1e9, modify(1, 1, n);
        L = s[++*s] = j, V = a[j] - 2 * j, modify(1, 1, n);
      }
      pre = r2;
    }
    int p = dicp(dicl(r1), c2);
    ans[id] = min(ans[id], 1 + abs(a[s[p]] - c2));
    if (p != *s) ans[id] = min(ans[id], 1 + abs(a[s[p + 1]] - c2));
    ans[id] += r2 - r1;
    int r = dicr(r1);
    if (r) {
      p = dic1(1, r, c2);
      if (p)
        ans[id] =
            min(ans[id], r1 + r2 - 2 * s[p] + c2 - a[s[p]] + (c1 < a[s[p]]));
      if (p < r) {
        int p1 = dic1(p + 1, r, c1);
        if (p1 >= p + 1)
          L = s[p + 1], R = s[p1],
          ans[id] = min(ans[id], query(1, 1, n) + r1 + r2 - c2);
        if (p1 + 1 <= r)
          L = s[p1 + 1], R = s[r],
          ans[id] = min(ans[id], query(1, 1, n) + 1 + r1 + r2 - c2);
      }
    }
  }
  *s = 0;
  memset(t, 60, sizeof t);
  for (int i = cnt[ID], pre = n + 1; i >= 1; i--) {
    int r1 = q[ID][i].r1, c1 = min(q[ID][i].c1, q[ID][i].mn), r2 = q[ID][i].r2,
        c2 = q[ID][i].c2, id = q[ID][i].id;
    if (pre > r2) {
      for (int j = pre - 1, _y = r2; j >= _y; j--) {
        for (; *s > 0 && a[s[*s]] >= a[j]; --*s)
          L = s[*s], V = 1e9, modify(1, 1, n);
        L = s[++*s] = j, V = 2 * j + a[j], modify(1, 1, n);
      }
      pre = r2;
    }
    int r = dicr_(r2);
    if (r) {
      int p = dic1(1, r, c2);
      if (p)
        ans[id] =
            min(ans[id], 2 * s[p] - r2 - r1 + c2 - a[s[p]] + (c1 < a[s[p]]));
      if (p < r) {
        int p1 = dic1(p + 1, r, c1);
        if (p1 >= p + 1)
          R = s[p + 1], L = s[p1],
          ans[id] = min(ans[id], query(1, 1, n) - r2 - r1 - c2);
        if (p1 + 1 <= r)
          R = s[p1 + 1], L = s[r],
          ans[id] = min(ans[id], query(1, 1, n) + 1 - r2 - r1 - c2);
      }
    }
  }
}
int main() {
  n = read();
  for (int i = 1, _y = n; i <= _y; i++) a[i] = read();
  build(1, 1, n);
  m = read();
  for (int i = 1, _y = m; i <= _y; i++) {
    int r1 = read(), c1 = read(), r2 = read(), c2 = read(), mn;
    if (r1 < r2)
      L = r1 + 1, R = r2, mn = L <= R ? query(1, 1, n) : 1e9,
      q[0][++cnt[0]] = (node){r1, c1, r2, c2, i, mn};
    else
      L = r2, R = r1 - 1, mn = L <= R ? query(1, 1, n) : 1e9,
      q[1][++cnt[1]] = (node){n - r1 + 1, c1, n - r2 + 1, c2, i, mn};
  }
  sort(q[0] + 1, q[0] + cnt[0] + 1);
  work(0);
  reverse(a + 1, a + n + 1);
  sort(q[1] + 1, q[1] + cnt[1] + 1);
  work(1);
  for (int i = 1, _y = m; i <= _y; i++) write(ans[i]), puts("");
}
