题目描述

John 正在学校做物理实验，今天学习的是连通器原理：对于装有同种液体并且互相连通的一组容器，当液体稳定后，各容器中的液面会处于相同高度。

实验室中有 $n$ 个竖直圆柱形容器，底面积均为 $1$ 平方分米，高度可视为无限。容器编号为 $1$ 到 $n$。

相邻容器 $i$ 和 $i+1$ 在高度 $h_i$ 分米处由一条极细的管道相连。所有 $h_i$ 两两不同。

实验一共有 $t$ 组，且彼此独立。每次实验开始时所有容器都为空。

第 $i$ 次实验中，水被缓慢倒入容器 $a_i$。当任意正体积的水第一次出现在容器 $b_i$ 中时，实验结束。实验结果定义为在此之前一共倒入容器 $a_i$ 的水量，单位为升（也等价于立方分米）。

注意，只有当相邻两个容器中的水位都至少达到连接高度 $h_i$ 时，它们之间才能按照连通器原理平衡。在此之前，如果只有一侧的水位到达 $h_i$，该侧水位会保持在 $h_i$，继续流入的水会通过管道流到另一侧。

请计算每次实验的结果。

输入格式

第一行输入一个整数 $n$：

第二行输入 $n-1$ 个整数

其中

且所有 $h_i$ 两两不同。

第三行输入一个整数 $t$，表示实验数量：

接下来 $t$ 行，每行输入两个整数 $a_i,b_i$：

输出格式

对每组实验输出一个整数，表示需要倒入的水量。

样例

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

25
18
14
12