题目描述

给定一个长度为 $N$ 的序列 $H$ 和 $Q$ 次询问。

第 $i$ 次询问中，你初始在第 $S_i$ 列 $H_{S_i}$ 行，想要到第 $T_i$ 列第 $H_{T_i}$ 行。

你可以进行若干次移动。每次移动你可以选择以下两种参数：

• 列 $-1$，列不变，列 $+1$。
• 行 $-1$，行不变，行 $+1$。

如果你选择行 $-1$，消耗 $1$ 体力，如果你选择行不变，消耗 $2$ 体力，如果你选择行 $+1$，消耗 $4$ 体力。

你需要保证每次移动后，你的列数 $x$ 在 $[1,N]$ 之间，且你的行数 $y$ 不小于 $H_x$。

对于每个询问，你需要求出你消耗体力的最小值。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $H_i$。

接下来 $Q$ 行，每行输入两个正整数 $S_i,T_i$。

输出格式

对于每个询问，输出一行，包含一个整数，代表消耗体力的最小值。

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

提示

【样例解释】

以下为第一个样例中两个询问的图示：

【数据范围】

• Subtask 1（7 points）：只存在一组数据，满足 $N=8$，$Q=4$，$H=[,9,3,3,5,4,8,2]$，$(S_i,T_i)$ 依次为 $(1,8)$，$(3,6)$，$(6,4)$ 和 $(7,2)$。
• 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）：无特殊限制。

对于所有数据，$2\leq N\leq 2\times 10^5$，$H_i\leq 10^9$，$Q\leq 2\times 10^5$，$1\leq S_i,T_i\leq N$。