問題文

N + 2 枚の皿が一列に並んでいます。これらの皿を左から順に皿 0, 皿 1, ..., 皿 N+1 と番号づけます。皿 1 から皿 N までの N 枚の皿にはそれぞれ飴玉がいくつか乗っており、皿 0 と皿 N+1 には飴玉は乗っていません。

ニワンゴくんとニコニコテレビちゃんはこれらの飴玉を次のようにしてふたりで分けようとしています。

1. 皿 1 から皿 N までのそれぞれの皿について、その皿に乗っている飴玉をすべて左隣か右隣の皿へ移す。この移動は、各皿について左右の方向を決めたあとにすべて同時に行う。
2. 飴玉の乗っていない皿をすべて列から取り除く。
3. 残った皿のうち、左から奇数番目 (1, 3, 5, ... 番目) の皿に乗っている飴玉をニワンゴくんが、左から偶数番目 (2, 4, 6, ... 番目) の皿に乗っている飴玉をニコニコテレビちゃんがもらう。

ニワンゴくんはできるだけ多くの飴玉をもらえるように手順 1 での飴玉の移動方向を決めたいと思っています。ニワンゴくんのために、以下のようなプログラムを作って下さい。

最初、皿 i (1 ≦ i ≦ N) には A_i 個の飴玉が乗っているとします。その後、飴玉の個数を変化させるクエリが Q 個与えられるので順番に処理してください。j (1 ≦ j ≦ Q) 番目のクエリは 2 個の整数 K_j と X_j からなり、皿 K_j に乗っている飴玉の個数を X_j 個に変えることを表しています。

各 j (1 ≦ j ≦ Q) に対し、j 個目までのクエリを処理した状態からニワンゴくんとニコニコテレビちゃんが上記の方法で飴玉を分けるとき、ニワンゴくんがもらえる飴玉の個数の最大値を出力して下さい。

制約

• 1≦N≦5 \times 10^4
• 1≦A_i≦10^4
• 1≦Q≦5 \times 10^4
• 1≦K_j≦N
• 1≦X_j≦10^4

部分点

• Q=1 を満たすデータセットに正解した場合は、700 点が与えられる。

入力例 1

6
3 1 4 1 5 9
1
1 3

出力例 1

21

部分点の条件を満たすケースです。はじめ、皿に乗っている飴玉の個数は左の皿からそれぞれ 0, 3, 1, 4, 1, 5, 9, 0 です。

ここで、皿 1 から 6 について、乗っている飴玉をそれぞれ右・右・左・右・左・右隣の皿へと移すと、飴玉の個数は 0, 0, 7, 1, 5, 1, 0, 9 となります。

次に飴玉の乗っていない皿をすべて取り除くと 7, 1, 5, 1, 9 となり、左から奇数番目の皿に乗っている飴玉の合計個数は 21 となります。このケースではこれがニワンゴくんが最も多くの飴玉をもらえるパターンです。

入力例 2

5
1 2 3 4 5
1
1 1

出力例 2

11

部分点の条件を満たすケースです。

入力例 3

8
2 5 2 5 2 5 2 5
5
1 7
6 1
3 6
8 3
2 9

出力例 3

27
24
24
22
26

この入出力例は部分点の条件を満たしません。