Niwango 和 Nikomoba 玩以下遊戲。

有 $N$ 枚硬幣排成一列，編號從 $1$ 到 $N$。最初，奇數編號的硬幣正面朝上，偶數編號的硬幣反面朝上。第 $i$ 枚硬幣的價值為 $S_i$。

遊戲共有 $N - 1$ 個回合，回合編號從 $1$ 到 $N - 1$。Niwango 在奇數編號的回合行動，Nikomoba 在偶數編號的回合行動。在第 $i$ 個回合，玩家可以將第 $i$ 枚和第 $i + 1$ 枚硬幣中的至多一枚翻面。（玩家也可以不翻任何硬幣。）

經過 $N - 1$ 個回合後，Niwango 取走所有正面朝上的硬幣，Nikomoba 取走所有反面朝上的硬幣。玩家的得分為他取走的所有硬幣的價值總和。求兩位玩家都採取最佳策略時 Niwango 的得分。

此外，硬幣的價值將有 $Q$ 次更新。在第 $i$ 次更新中，第 $P_i$ 枚硬幣的價值減少 $D_i$。此次更新在之後的所有更新中持續生效；例如，第二次更新後，前兩次更新均已生效。對每個 $i$，假設他們在第 $i$ 次更新後才開始遊戲，求 Niwango 的得分。

輸入格式

$$ \begin{gathered} N \\ S_1\ \ldots\ S_N \\ Q \\ P_1\ D_1 \\ \vdots \\ P_Q\ D_Q \end{gathered} $$

• $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