Dreamoon has just created a document of hard problems using notepad.exe. The document consists of n lines of text, ai denotes the length of the i-th line. He now wants to know what is the fastest way to move the cursor around because the document is really long.

Let (r, c) be a current cursor position, where r is row number and c is position of cursor in the row. We have 1 ≤ r ≤ n and 0 ≤ c ≤ ar.

We can use following six operations in notepad.exe to move our cursor assuming the current cursor position is at (r, c):

  1. up key: the new cursor position (nr, nc) = (max(r - 1, 1), min(anr, c))
  2. down key: the new cursor position (nr, nc) = (min(r + 1, n), min(anr, c))
  3. left key: the new cursor position (nr, nc) = (r, max(0, c - 1))
  4. right key: the new cursor position (nr, nc) = (r, min(anr, c + 1))
  5. HOME key: the new cursor position (nr, nc) = (r, 0)
  6. END key: the new cursor position (nr, nc) = (r, ar)



You're given the document description (n and sequence ai) and q queries from Dreamoon. Each query asks what minimal number of key presses is needed to move the cursor from (r1, c1) to (r2, c2).

Input

The first line contains an integer n(1 ≤ n ≤ 400, 000) — the number of lines of text. 

The second line contains n integers a1, a2, ..., an(1 ≤ ai ≤ 108).

The third line contains an integer q(1 ≤ q ≤ 400, 000). 

Each of the next q lines contains four integers r1, c1, r2, c2 representing a query (1 ≤ r1, r2 ≤ n, 0 ≤ c1 ≤ ar1, 0 ≤ c2 ≤ ar2).

Output

For each query print the result of the query.

Examples

Input

9
1 3 5 3 1 3 5 3 1
4
3 5 3 1
3 3 7 3
1 0 3 3
6 0 7 3


Output

2
5
3
2


Input

2
10 5
1
1 0 1 5


Output

3

Note

In the first sample, the first query can be solved with keys: HOME, right.

The second query can be solved with keys: down, down, down, END, down.

The third query can be solved with keys: down, END, down.

The fourth query can be solved with keys: END, down.
#include <bits/stdc++.h>
using namespace std;
const int Inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
const int qwq = 1 << 19;
int N, Q;
int a[qwq];
struct Query {
  int r1, c1, r2, c2, id;
  Query(int r1, int c1, int r2, int c2, int id)
      : r1(r1), c1(c1), r2(r2), c2(c2), id(id) {}
  bool inline operator<(const Query &a) const { return r2 < a.r2; }
};
struct Segtree {
  int dt[qwq << 1];
  void inline init() { memset(dt, Inf, sizeof(dt)); }
  void inline add(int a, int x) {
    a += qwq;
    dt[a] = x;
    while (a >>= 1) dt[a] = min(dt[a << 1], dt[a << 1 | 1]);
  }
  int inline get(int l, int r) {
    int res = Inf;
    for (l += qwq, r += qwq + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = min(res, dt[l++]);
      if (r & 1) res = min(res, dt[--r]);
    }
    return res;
  }
} sl, sr, qj;
vector<Query> q1, q2;
int ans[qwq];
vector<int> dd;
int inline mianx(int a, int l, int r) { return max(min(a, r), l); }
int inline Ubval(int val) {
  int l = -1, r = ((int)(dd).size());
  while (r - l > 1) {
    int m = (l + r) >> 1;
    if (a[dd[m]] > val)
      r = m;
    else
      l = m;
  }
  return r;
}
int inline Lbpos(int val) {
  return lower_bound((dd).begin(), (dd).end(), val) - dd.begin();
}
int inline FLbpos(int val) {
  return upper_bound((dd).begin(), (dd).end(), val, greater<int>()) -
         dd.begin();
}
void inline solve() {
  int qid = 0;
  sl.init();
  sr.init();
  qj.init();
  for (int i = 1; i <= (N); ++i) qj.add(i, a[i]);
  for (int i = 1; i <= (N); ++i) {
    while (((int)(dd).size()) && a[dd.back()] >= a[i]) dd.pop_back();
    sl.add(((int)(dd).size()), a[i] - 2 * i);
    sr.add(((int)(dd).size()), -a[i] - 2 * i);
    int rp = ((int)(dd).size());
    dd.push_back(i);
    while (qid < ((int)(q1).size()) && q1[qid].r2 == i) {
      int id = q1[qid].id;
      int r1 = q1[qid].r1, c1 = q1[qid].c1;
      int r2 = q1[qid].r2, c2 = q1[qid].c2;
      int lp = Lbpos(r1);
      ans[id] = min(ans[id], r2 - r1 + c2 + 1);
      ans[id] = min(ans[id], r2 - r1 + abs(min(c1, a[dd[lp]]) - c2));
      int rpos = Ubval(c2), lpos = rpos - 1, pos;
      rpos = mianx(rpos, lp, rp);
      lpos = mianx(lpos, lp, rp);
      if (abs(a[dd[lpos]] - c2) < abs(a[dd[rpos]] - c2))
        pos = lpos;
      else
        pos = rpos;
      ans[id] = min(ans[id], r2 - r1 + abs(a[dd[pos]] - c2) + 1);
      rpos = Ubval(c2), lpos = rpos - 1;
      rpos = mianx(rpos, 0, lp);
      lpos = mianx(lpos, -1, lp - 1);
      ans[id] = min(ans[id], r2 + r1 + sr.get(0, lpos) + c2 + 1);
      ans[id] = min(ans[id], r2 + r1 + sl.get(rpos, lp - 1) - c2 + 1);
      int sp = min(Ubval(min(c1, a[dd[lp]])), lp);
      rpos = Ubval(c2), lpos = rpos - 1;
      rpos = mianx(rpos, 0, sp);
      lpos = mianx(lpos, -1, sp - 1);
      ans[id] = min(ans[id], r2 + r1 + sr.get(0, lpos) + c2);
      ans[id] = min(ans[id], r2 + r1 + sl.get(rpos, sp - 1) - c2);
      ++qid;
    }
  }
  dd.clear();
  sl.init();
  sr.init();
  --qid;
  for (int i = (N); ((-1) > 0 ? i <= (1) : i >= (1)); i += (-1)) {
    while (((int)(dd).size()) && a[dd.back()] >= a[i]) dd.pop_back();
    sl.add(((int)(dd).size()), a[i] + 2 * i);
    sr.add(((int)(dd).size()), -a[i] + 2 * i);
    int rp = ((int)(dd).size());
    dd.push_back(i);
    while (~qid && q1[qid].r2 == i) {
      int id = q1[qid].id;
      int r1 = q1[qid].r1, c1 = q1[qid].c1;
      int r2 = q1[qid].r2, c2 = q1[qid].c2;
      int rpos = Ubval(c2), lpos = rpos - 1;
      rpos = mianx(rpos, 0, rp + 1);
      lpos = mianx(lpos, -1, rp);
      ans[id] = min(ans[id], sr.get(0, lpos) + c2 - r2 - r1 + 1);
      ans[id] = min(ans[id], sl.get(rpos, rp) - c2 - r2 - r1 + 1);
      int sp = min(Ubval(min(qj.get(r1, r2), c1)), rp);
      rpos = Ubval(c2), lpos = rpos - 1;
      rpos = mianx(rpos, 0, sp);
      lpos = mianx(lpos, -1, sp - 1);
      ans[id] = min(ans[id], sr.get(0, lpos) + c2 - r2 - r1);
      ans[id] = min(ans[id], sl.get(rpos, sp - 1) - c2 - r2 - r1);
      --qid;
    }
  }
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= (N); ++i) scanf("%d", a + i);
  scanf("%d", &Q);
  memset(ans, Inf, sizeof(ans));
  for (int i = 1; i <= (Q); ++i) {
    int r1, c1, r2, c2;
    scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
    if (r1 <= r2)
      q1.push_back(Query(r1, c1, r2, c2, i));
    else
      q2.push_back(Query(N - r1 + 1, c1, N - r2 + 1, c2, i));
  }
  sort((q1).begin(), (q1).end());
  solve();
  reverse(a + 1, a + N + 1);
  sort((q2).begin(), (q2).end());
  q2.swap(q1);
  solve();
  for (int i = 1; i <= (Q); ++i) printf("%d\n", ans[i]);
  return 0;
}
