Problem Description

You are given a sequence $H$ of length $N$ and $Q$ queries.

In the $i$-th query, you start at column $S_i$ and row $H_{S_i}$, and you want to reach column $T_i$ and row $H_{T_i}$.

You may make several moves. In each move, you can choose the following two parameters:

• Column $-1$, column unchanged, column $+1$.
• Row $-1$, row unchanged, row $+1$.

If you choose row $-1$, it costs $1$ stamina. If you choose row unchanged, it costs $2$ stamina. If you choose row $+1$, it costs $4$ stamina.

You must ensure that after each move, your column index $x$ is within $[1,N]$, and your row index $y$ is not less than $H_x$.

For each query, find the minimum stamina cost.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ positive integers $H_i$.

The third line contains a positive integer $Q$.

The next $Q$ lines each contain two positive integers $S_i, T_i$.

Output Format

For each query, output one line containing an integer, the minimum stamina cost.

4
9 1 8 2
2
1 3
4 2

3
31

9
1 2 3 2 1 2 3 2 1
4
1 9
4 6
2 6
5 2

18
4
9
9

Hint

Sample Explanation

The following figures illustrate the two queries in the first sample:

Constraints

• Subtask 1 (7 points): There is only one set of testdata, where $N=8$, $Q=4$, $H=[,9,3,3,5,4,8,2]$, and $(S_i,T_i)$ are $(1,8)$, $(3,6)$, $(6,4)$, and $(7,2)$ in order.
• Subtask 2 (5 points): $S_i+1=T_i$.
• Subtask 3 (6 points): $H_i=i$.
• Subtask 4 (18 points): $N,Q,H_i\leq 100$.
• Subtask 5 (24 points): $N,Q\leq 1000$.
• Subtask 6 (13 points): $S_i=1$.
• Subtask 7 (27 points): No special restrictions.

For all testdata, $2\leq N\leq 2\times 10^5$, $H_i\leq 10^9$, $Q\leq 2\times 10^5$, and $1\leq S_i,T_i\leq N$.

Translated by ChatGPT 5