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):

1. up key: the new cursor position (nr,nc)=(max(r-1,1),min(a_nr,c))
2. down key: the new cursor position (nr,nc)=(min(r+1,n),min(a_nr,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(a_nr,c+1))
5. HOME key: the new cursor position (nr,nc)=(r,0)
6. 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₂).

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).

For each query print the result of the query.