有 $N + 2$ 个城镇排成一条直线。城镇从左到右编号为 $0$ 到 $N + 1$。每个城镇 $i$ ($1 \le i \le N$) 都有一个避难所，最多可容纳 $A_i$ 人。
目前，有 $S$ 个人正在一起旅行，并正在访问其中一个城镇。然而，你不知道他们具体在访问哪个城镇。
你刚刚得知有 $Q$ 颗陨石可能会袭击这些城镇。第 $i$ 颗陨石可能会袭击城镇 $L_i, L_i + 1, \dots, R_i$。为了确保旅行者的安全，对于每一颗陨石，你需要计算其疏散成本。
陨石的疏散成本计算如下：
- 疏散成本是指，无论旅行者当前正在访问哪个城镇，为了使所有旅行者都安全所需的最少总成本。
- 如果一个人在避难所中，或者在受陨石影响范围之外的城镇，则该人是安全的。
- 将一个人移动到相邻城镇需要 $1$ 单位成本（当且仅当两个城镇的编号相差恰好为 $1$ 时，它们是相邻的）。
注意，只有移动人员需要花费成本，其他操作（如将人员安置在避难所中）不需要成本。保证城镇 $0$ 和 $N + 1$ 永远不会受到陨石影响，因此总能使所有旅行者安全。
编写一个程序，为每一颗陨石计算其疏散成本。
输入格式
输入通过标准输入按以下格式给出：
$N \ S$ $A_1 \ A_2 \dots A_N$ $Q$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_Q \ R_Q$
数据范围
- $1 \le N \le 2 \times 10^5$
- $1 \le S \le 10^{12}$
- $0 \le A_i \le S$
- $A_1 + A_2 + \dots + A_N \le 10^{12}$
- $1 \le Q \le 2 \times 10^5$
- $1 \le L_i \le R_i \le N$
- 输入中的所有值均为整数。
输出格式
输出 $Q$ 行。第 $i$ 行应包含第 $i$ 颗陨石的疏散成本。
样例
输入 1
5 10 3 1 1 4 1 3 1 4 3 5 2 5
输出 1
14 10 13
说明
- 对于第一颗陨石，当旅行者正在访问城镇 $2$ 时，需要 $14$ 单位成本。
- 对于第二颗陨石，当旅行者正在访问城镇 $4$ 时，需要 $10$ 单位成本。
- 对于第三颗陨石，当旅行者正在访问城镇 $3$ 时，需要 $13$ 单位成本。