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*_{1}, *c*_{1})$ to $(*r*_{2}, *c*_{2})$.

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*_{1}, *a*_{2}, ..., *a*_{*n*}(1 ≤ *a*_{*i*} ≤ 10^{8})$.

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

Each of the next $*q*$ lines contains four integers $*r*_{1}, *c*_{1}, *r*_{2}, *c*_{2}$ representing a query ($1 ≤ *r*_{1}, *r*_{2} ≤ *n*, 0 ≤ *c*_{1} ≤ *a*_{*r*1}, 0 ≤ *c*_{2} ≤ *a*_{*r*2}$).

Output

For each query print the result of the query.

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.