Dreamoon and Notepad
Description
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):
- up key: the new cursor position (nr, nc) = (max(r - 1, 1), min(anr, c))
- down key: the new cursor position (nr, nc) = (min(r + 1, n), min(anr, c))
- left key: the new cursor position (nr, nc) = (r, max(0, c - 1))
- right key: the new cursor position (nr, nc) = (r, min(anr, c + 1))
- HOME key: the new cursor position (nr, nc) = (r, 0)
- 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).
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).
For each query print the result of the query.
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.
Samples
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
2
5
3
2
2
10 5
1
1 0 1 5
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.