Niwango 和 Nikomoba 正在玩一个游戏。

有 $N$ 枚硬币排成一行，编号从 $1$ 到 $N$。初始时，奇数编号的硬币正面朝上，偶数编号的硬币背面朝上。第 $i$ 枚硬币的价值为 $S_i$。

游戏共进行 $N-1$ 轮，轮次编号从 $1$ 到 $N-1$。Niwango 在奇数轮进行操作，Nikomoba 在偶数轮进行操作。在第 $i$ 轮，当前玩家最多可以翻转 $i$ 和 $i+1$ 号硬币中的一枚。（玩家也可以选择不翻转任何硬币）。

在 $N-1$ 轮结束后，Niwango 拿走所有正面朝上的硬币。玩家的得分是他所拿走硬币的价值之和。假设双方均采取最优策略，计算 Niwango 的得分。

此外，会有 $Q$ 次硬币价值的更新。在第 $i$ 次更新中，硬币 $P_i$ 的价值减少 $D_i$。此更新对后续所有操作均有效；例如，在第二次更新后，前两次更新均已生效。对于每次更新，请计算在第 $i$ 次更新后开始游戏时，Niwango 的得分。

输入格式

$N$ $S_1 \dots S_N$ $Q$ $P_1 \ D_1$ $\vdots$ $P_Q \ D_Q$

数据范围

• $2 \le N \le 200000$
• $1 \le S_i \le 10^9$
• $0 \le Q \le 200000$
• $1 \le P_i \le N$
• $1 \le D_i$
• 在任何时刻，每枚硬币的价值均为正数。

输出格式

输出 $Q+1$ 行。第 $i$ 行输出在经过 $(i-1)$ 次硬币价值更新后，开始游戏时 Niwango 的得分。

样例

样例输入 1

4
1 2 3 4
1
4 3

样例输出 1

7
5

样例输入 2

8
3 1 4 1 5 9 2 6
5
3 3
6 6
8 4
1 1
6 2

样例输出 2

19
16
16
12
11
11