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 \le r \le n and 0 \le c \le 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 \le n \le 400,000) - the number of lines of text.
The second line contains n integers a1,a2,...,an(1 \le ai \le 108).
The third line contains an integer q(1 \le q \le 400,000).
Each of the next q lines contains four integers r1,c1,r2,c2 representing a query (1 \le r1,r2 \le n,0 \le c1 \le ar1,0 \le c2 \le ar2).
For each query print the result of the query.
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\n · · · · · · · · \n \n · · · \n · · · \n · · · \n · · · \n
2 5 3 2\n \n \n \n
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.