Dreamoon and Notepad

3000ms

262144K

Description:

Dreamoon has just created a document of hard problems using notepad.exe. The document consists of n lines of text, a_i 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 ≤ a_r.

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(a_nr, c))
down key: the new cursor position (nr, nc) = (min(r + 1, n), min(a_nr, c))
left key: the new cursor position (nr, nc) = (r, max(0, c - 1))
right key: the new cursor position (nr, nc) = (r, min(a_nr, c + 1))
HOME key: the new cursor position (nr, nc) = (r, 0)
END key: the new cursor position (nr, nc) = (r, a_r)

You're given the document description (n and sequence a_i) and q queries from Dreamoon. Each query asks what minimal number of key presses is needed to move the cursor from (r₁, c₁) to (r₂, c₂).

Input:

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

The second line contains n integers a₁, a₂, ..., a_n(1 ≤ a_i ≤ 10⁸).

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

Each of the next q lines contains four integers r₁, c₁, r₂, c₂ representing a query (1 ≤ r₁, r₂ ≤ n, 0 ≤ c₁ ≤ a_r1, 0 ≤ c₂ ≤ a_r2).

Output:

For each query print the result of the query.

Sample 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

Sample Output:

Sample Input:

Sample Output:

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.

Informação

Provedor Codeforces

Código CF477E