问题文

小乌龟和尼科萌正在玩一个使用硬币的游戏。

一开始有 $N$ 个硬币排成一列，从左到右依次编号为 $1$ 到 $N$。奇数号的硬币正面朝上，偶数号的硬币反面朝上。硬币 $i$ 的价值是 $S_i$。

这个游戏由 $N-1$ 轮组成，奇数轮由小乌龟玩，偶数轮由尼科萌玩。在第 $i$ 轮中，玩家可以翻转硬币 $i$ 或者硬币 $i+1$。如果不想翻转任何一个硬币，也是可以的。

在进行完 $N-1$ 轮后，小乌龟可以获得正面朝上的硬币，而尼科萌可以获得反面朝上的硬币。此时，玩家的得分就是他们所获得的硬币的价值之和。问小乌龟的得分是多少？假设两个玩家都很聪明，会选择最优的策略来使自己的得分最大化。

另外，在开始游戏之前，尼科萌对硬币进行了一些涂鸦，导致硬币的价值下降。尼科萌进行了 $Q$ 次涂鸦，第 $i$ 次涂鸦是在硬币 $P_i$ 上进行的，导致硬币 $P_i$ 的价值下降了 $D_i$。

请计算在每次涂鸦之后立即开始游戏时小乌龟的得分。

---

输入

输入以以下格式从标准输入中给出。

$N$

$S_1$ $S_2$ ... $S_N$

$Q$

$P_1$ $D_1$

$P_2$ $D_2$

...

$P_Q$ $D_Q$

• 第一行为一个整数 $N (2 ≦ N ≦ 200,000)$，表示硬币的数量。
• 第二行为 $N$ 个整数，以空格分隔，表示初始硬币的价值。其中第 $i$ 个整数 $S_i (1 ≦ S_i ≦ 10^9)$ 表示硬币 $i$ 的初始价值。
• 第三行为一个整数 $Q (0 ≦ Q ≦ 200,000)$，表示尼科萌进行涂鸦的次数。
• 接下来的 $Q$ 行，每行有两个整数 $P_i (1 ≦ P_i ≦ N), D_i (1 ≦ D_i)$，以空格分隔。这表示第 $i$ 次涂鸦导致硬币 $P_i$ 的价值下降了 $D_i$。每个硬币的价值始终大于等于 $1$。

部分分

本问题设有部分分。

• 当满足 $Q = 0$ 的数据集 $1$ 的正确答案时，得到 $10$ 分。
• 当满足 $S_i ≦ 25$ 的数据集 $2$ 的正确答案时，除上述之外再得到 $80$ 分。
• 当对所有测试用例都给出正确答案时，除上述之外再得到 $90$ 分。

输出

输出包含 $Q+1$ 行。第一行输出从初始状态开始游戏时小乌龟的得分，接下来的 $Q$ 行中，第 $i$ 行输出第 $i$ 次涂鸦之后立即开始游戏时小乌龟的得分。输出末尾要有换行符。

---

示例1

4
1 2 3 4
1
4 3

输出示例1

7
5

这个例子中，有 $4$ 个硬币，它们的价值从左到右依次为 $1,2,3,4$。一开始，硬币的上面是 "正反正反"。如果从这个状态开始游戏，会有以下操作：

• 小乌龟翻转硬币 $2$ → 尼科萌翻转硬币 $3$ → 小乌龟翻转硬币 $4$

最后，硬币的上面是 "正正反正"，所以小乌龟得分为 $7$。

此外，这个例子中有 $1$ 个查询。查询导致硬币 $4$ 的价值下降为 $1$。如果从这个状态开始游戏，会有以下操作：

• 小乌龟翻转硬币 $2$ → 尼科萌翻转硬币 $2$ → 小乌龟翻转硬币 $4$

最后，硬币的上面是 "正反正正"，所以小乌龟得分为 $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