John 正在学校进行物理实验。今天他正在研究连通器原理。该原理指出，如果我们有一组装有均匀液体的连通容器，当液体静止时，无论容器的形状和体积如何，所有容器中的液面都会达到相同的高度。

在实验室里，John 有 $n$ 个圆柱形容器，底面积为 1 平方分米，高度视为无限高。容器编号从 1 到 $n$，容器 $i$ 和 $i+1$ 通过一个高度为 $h_i$ 分米的极细桥相连。所有这些高度 $h_i$ 两两不同。

实验包含 $t$ 次独立的实验。在每次实验中，所有容器初始均为空。在第 $i$ 次实验中，水被缓慢注入容器 $a_i$，当容器 $b_i$ 中出现任何水时，实验结束。实验结果是注入容器 $a_i$ 的水的总体积，单位为升（等同于立方分米）。

注意，连通器原理仅在容器 $i$ 和 $i+1$ 中的水位都至少达到 $h_i$ 时才适用。在此之前，如果水位仅在其中一个容器中达到 $h_i$，则该容器的水位保持不变，任何多余流入该容器的水都会通过桥流向另一个容器。

请帮助 John 检查他的实验结果！

输入格式

第一行包含一个整数 $n$ —— 容器的数量 ($2 \le n \le 2 \cdot 10^5$)。

第二行包含 $n-1$ 个整数 $h_1, h_2, \dots, h_{n-1}$ —— 相邻容器之间连通桥的高度，单位为分米 ($1 \le h_i \le 10^9$)。这些高度两两不同。

第三行包含一个整数 $t$ —— 实验次数 ($1 \le t \le 2 \cdot 10^5$)。

接下来的 $t$ 行，每行包含两个整数 $a_i$ 和 $b_i$ —— 第 $i$ 次实验中起始容器和目标容器的编号 ($1 \le a_i \le n; 1 \le b_i \le n; a_i \neq b_i$)。

输出格式

对于每次实验，按输入顺序输出一个整数 —— 所需的水的体积，单位为升。

样例

样例输入 1

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

样例输出 1

25
18
14
12