E. Dreamoon and Notepadtime limit per test3.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputDreamoon 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).InputThe 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).OutputFor each query print the result of the query.ExamplesInput91 3 5 3 1 3 5 3 143 5 3 13 3 7 31 0 3 36 0 7 3Output2532Input210 511 0 1 5Output3NoteIn 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.
Input91 3 5 3 1 3 5 3 143 5 3 13 3 7 31 0 3 36 0 7 3
Output2532
['data structures', '*3100']