Niwango と Nikomoba は次のゲームをします。

$N$ 枚のコインが一列に並んでおり、$1$ から $N$ までの番号が付けられています。最初、奇数番目のコインは表向き、偶数番目のコインは裏向きです。コイン $i$ の価値は $S_i$ です。

ゲームは $N-1$ 回の手番からなり、手番には $1$ から $N-1$ までの番号が付けられています。奇数番目の手番では Niwango が、偶数番目の手番では Nikomoba が操作します。手番 $i$ では、プレイヤーはコイン $i$ と $i+1$ のうち高々1枚を裏返すことができます。（どのコインも裏返さなくてもかまいません。）

$N-1$ 回の手番が終わると、Niwango は表向きのコインをすべて取り、Nikomoba は裏向きのコインをすべて取ります。プレイヤーの得点は、取ったコインすべての価値の合計です。両者が最適にプレイした場合の Niwango の得点を求めてください。

また、コインの価値を $Q$ 回更新します。$i$ 回目の更新では、コイン $P_i$ の価値が $D_i$ だけ減少します。この更新はそれ以降のすべての更新でも有効です。例えば、2回目の更新後には、最初の2回の更新が両方とも適用されています。各 $i$ について、$i$ 回目の更新後にゲームを始めると仮定した場合の Niwango の得点を求めてください。

入力

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

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