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