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>
void LilyWhite(const char *s) {
  static char filename[32];
  sprintf(filename, "%s.in", s);
  freopen(filename, "r", stdin);
  sprintf(filename, "%s.out", s);
  freopen(filename, "w", stdout);
}
class Reader {
 private:
  static const int BUF_SIZE = 1 << 22;
  char BUF_R[BUF_SIZE], *csy1, *csy2;

 public:
  inline bool eof() {
    return csy1 == csy2 &&
           (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
            csy1 == csy2);
  }
  template <class Ty>
  inline Reader &operator>>(Ty &t) {
    int u = 0;
    char c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                       csy1 == csy2)
                  ? EOF
                  : *csy1++);
    for (t = 0; c < 48 || c > 57;
         c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                      csy1 == csy2)
                  ? EOF
                  : *csy1++))
      if (c == EOF)
        break;
      else if (c == '-')
        u = 1;
    for (; c > 47 && c < 58;
         c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                      csy1 == csy2)
                  ? EOF
                  : *csy1++))
      t = (t << 1) + (t << 3) + (c ^ 48);
    t = u ? -t : t;
    return *this;
  }
  inline Reader &operator>>(double &t) {
    int tmp, u = 0;
    char c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                       csy1 == csy2)
                  ? EOF
                  : *csy1++);
    for (tmp = 0; c < 48 || c > 57;
         c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                      csy1 == csy2)
                  ? EOF
                  : *csy1++))
      if (c == EOF)
        break;
      else if (c == '-')
        u = 1;
    for (; c > 47 && c < 58;
         c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                      csy1 == csy2)
                  ? EOF
                  : *csy1++))
      tmp = (tmp << 1) + (tmp << 3) + (c ^ 48);
    t = (tmp = u ? -tmp : tmp);
    if (c == '.') {
      double x = 1;
      for (c = (csy1 == csy2 && (csy2 = (csy1 = BUF_R) +
                                        fread(BUF_R, 1, BUF_SIZE, stdin),
                                csy1 == csy2)
                    ? EOF
                    : *csy1++);
           c > 47 && c < 58;
           c = (csy1 == csy2 && (csy2 = (csy1 = BUF_R) +
                                        fread(BUF_R, 1, BUF_SIZE, stdin),
                                csy1 == csy2)
                    ? EOF
                    : *csy1++))
        t += (x /= 10) * (c ^ 48);
    }
    return *this;
  }
  inline Reader &operator>>(char *s) {
    char c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                       csy1 == csy2)
                  ? EOF
                  : *csy1++);
    for (*s = 0; c < 33;
         c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                      csy1 == csy2)
                  ? EOF
                  : *csy1++))
      if (c == EOF) return *this;
    for (; c > 32;
         c = (csy1 == csy2 &&
                      (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin),
                      csy1 == csy2)
                  ? EOF
                  : *csy1++))
      *s++ = c;
    *s = 0;
    return *this;
  }
} Mizuhashi;
class Writer {
 private:
  static const int BUF_SIZE = 1 << 22;
  char BUF_W[BUF_SIZE], *csy;
  inline void WC(const char c) {
    if (csy - BUF_W == BUF_SIZE)
      fwrite(BUF_W, 1, BUF_SIZE, stdout), csy = BUF_W;
    *csy++ = c;
  }

 public:
  Writer() : csy(BUF_W) {}
  ~Writer() { fwrite(BUF_W, 1, csy - BUF_W, stdout); }
  inline void flush() {
    fwrite(BUF_W, 1, csy - BUF_W, stdout);
    csy = BUF_W;
  }
  template <class Ty>
  inline Writer &operator<<(Ty x) {
    static int sta[32], top;
    if (x < 0) {
      WC('-');
      do sta[top++] = -(x % 10);
      while (x /= 10);
    } else
      do sta[top++] = x % 10;
      while (x /= 10);
    while (top) WC(sta[--top] ^ 48);
    return *this;
  }
  inline Writer &operator<<(const char &c) {
    WC(c);
    return *this;
  }
  inline Writer &operator<<(const char *s) {
    while (*s) WC(*s++);
    return *this;
  }
} Parsee;
template <class Ty>
inline void umin(Ty &x, const Ty &y) {
  x = x < y ? x : y;
}
template <class Ty>
inline void umax(Ty &x, const Ty &y) {
  x = x < y ? y : x;
}
using namespace std;
const int MAX_N = 400000 + 5;
const int INF32 = 0x3f3f3f3f;
int N, Q, a[MAX_N], minv[1 << 20], c[MAX_N], ans[MAX_N];
struct Node {
  int r1, c1, c2, idx;
  Node(int a = 0, int b = 0, int c = 0, int d = 0)
      : r1(a), c1(b), c2(c), idx(d) {}
};
vector<Node> q[2][MAX_N];
void segment_modify(int i, int l, int r, int x, int v) {
  if (l == r) {
    minv[i] = v;
    return;
  }
  int mid = (l + r) >> 1;
  mid < x ? segment_modify((i << 1 | 1), mid + 1, r, x, v)
          : segment_modify((i << 1), l, mid, x, v);
  umin(minv[i] = minv[(i << 1)], minv[(i << 1 | 1)]);
}
int segment_query(int i, int l, int r, int ql, int qr) {
  if (l < ql || r > qr) {
    int mid = (l + r) >> 1, res = INF32;
    if (mid >= ql) res = segment_query((i << 1), l, mid, ql, qr);
    if (mid < qr) umin(res, segment_query((i << 1 | 1), mid + 1, r, ql, qr));
    return res;
  } else
    return minv[i];
}
void solve(vector<Node> *q) {
  static int sta[MAX_N], num[MAX_N], top;
  top = 0;
  for (int i = 1; i <= N; i++) {
    while (top && a[i] <= num[top]) top--;
    top++;
    sta[top] = i;
    num[top] = a[i];
    segment_modify(1, 1, N, top, a[i] - (i << 1));
    for (vector<Node>::iterator it = q[i].begin(); it != q[i].end(); it++) {
      int r1 = it->r1, r2 = i, c1 = it->c1, c2 = it->c2, idx = it->idx, l;
      c[idx] = min(c1, num[l = lower_bound(sta + 1, sta + top + 1, r1) - sta]);
      umin(ans[idx], r2 - r1 + abs(c[idx] - c2));
      int pos = lower_bound(num + l, num + top + 1, c2) - num;
      if (pos <= top) umin(ans[idx], r2 - r1 + num[pos] - c2 + 1);
      if (pos > l)
        umin(ans[idx], r2 - r1 + c2 - num[pos - 1] + 1);
      else {
        pos = upper_bound(num + 1, num + top + 1, c2) - num - 1;
        if (pos && sta[pos] <= r1)
          umin(ans[idx],
               r1 + r2 - 2 * sta[pos] + c2 - num[pos] + (c1 < num[pos]));
        if (pos < l - 1) {
          int r = l - 1;
          l = pos + 1;
          pos = upper_bound(num + l, num + r + 1, c1) - num;
          if (pos <= r)
            umin(ans[idx], r1 + r2 + 1 + segment_query(1, 1, N, pos, r) - c2);
          if (l < pos)
            umin(ans[idx], r1 + r2 + segment_query(1, 1, N, l, pos - 1) - c2);
        }
      }
    }
  }
  top = 0;
  for (int i = N; i > 0; i--) {
    while (top && a[i] <= num[top]) top--;
    top++;
    sta[top] = i;
    num[top] = a[i];
    segment_modify(1, 1, N, top, a[i] + (i << 1));
    for (vector<Node>::iterator it = q[i].begin(); it != q[i].end(); it++) {
      int r1 = it->r1, r2 = i, c2 = it->c2, idx = it->idx;
      int pos = upper_bound(num + 1, num + top + 1, c2) - num - 1;
      if (pos)
        umin(ans[idx],
             sta[pos] * 2 - r1 - r2 + c2 - num[pos] + (c[idx] < num[pos]));
      if (pos < top) {
        int l = pos + 1;
        pos = upper_bound(num + l, num + top + 1, c[idx]) - num;
        if (pos <= top)
          umin(ans[idx], segment_query(1, 1, N, pos, top) - r1 - r2 + 1 - c2);
        if (l < pos)
          umin(ans[idx], segment_query(1, 1, N, l, pos - 1) - r1 - r2 - c2);
      }
    }
  }
}
int main() {
  Mizuhashi >> N;
  for (int i = 1; i <= N; i++) Mizuhashi >> a[i];
  Mizuhashi >> Q;
  for (int i = 1; i <= Q; i++) {
    int r1, c1, r2, c2;
    Mizuhashi >> r1 >> c1 >> r2 >> c2;
    ans[i] = abs(r1 - r2) + c2 + 1;
    if (r1 <= r2)
      q[0][r2].push_back(Node(r1, c1, c2, i));
    else
      q[1][N - r2 + 1].push_back(Node(N - r1 + 1, c1, c2, i));
  }
  solve(q[0]);
  reverse(a + 1, a + N + 1);
  solve(q[1]);
  for (int i = 1; i <= Q; i++) Parsee << ans[i] << '\n';
  return 0;
}
