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\quad D_1\\ \vdots\\ P_Q\quad 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