Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Dreamoon and Notepad

time limit per test

3.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDreamoon 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*_{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*_{r1}, 0 ≤ *c*_{2} ≤ *a*_{r2}).

Output

For each query print the result of the query.

Examples

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

Output

2

5

3

2

Input

2

10 5

1

1 0 1 5

Output

3

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.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2022 16:51:25 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|