P7974 [KSN2021] Delivering Balls

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.

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

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

**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