D - コインの取り合い Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

ニワンゴ君とニコモバちゃんはコインを使ったゲームをしています。

はじめ N 個のコインが 1 列に並んでいて、左から順に 1 から N の番号がついています。奇数番のコインは表、偶数番のコインは裏の面が上になっています。コイン i の価値は S_i です。

このゲームは N-1 ターンからなり、奇数ターン目のプレイヤーはニワンゴ君で、偶数ターン目のプレイヤーはニコモバちゃんです。i ターン目ではプレイヤーは、コイン i またはコイン i+1 のどちらかをひっくり返すことが出来ます。どちらもひっくり返したくない場合は、どちらもひっくり返さなくても良いです。

N-1 ターンが終わった後に、上を向いている面が表であるコインをニワンゴ君が、裏であるコインをニコモバちゃんが獲得します。このとき、自分が獲得したコインの価値の和がプレイヤーのスコアとなります。このとき、ニワンゴ君のスコアはいくつになるでしょうか？ただし、2 人はとても頭がいいので、それぞれが自分のスコアを最大化するような最適の戦略をとるものとします。

また、ゲームを始める前にニコモバちゃんがコインに落書きをしてしまい、コインの価値が下がってしまうことがあります。ニコモバちゃんは合計 Q 回落書きをして、i 回目に落書きしたコインはコイン P_i で、落書きによってコイン i の価値は D_i 下がりました。

Q 回の落書きそれぞれについても、落書きの直後にゲームを始めた場合のニワンゴ君のスコアを計算してください。

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 S_2 ... S_N
Q
P_1 D_1
P_2 D_2
:
P_Q D_Q
  • 1 行目には、コインの枚数を表す 1 つの整数 N (2 ≦ N ≦ 200,000) が与えられる。
  • 2 行目には、コインのはじめの価値を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 S_i (1 ≦ S_i ≦ 10^9) は、コイン i のはじめの価値を表す。
  • 3 行目には、ニコモバちゃんが落書きをした回数を表す 1 つの整数 Q (0 ≦ Q ≦ 200,000) が与えられる。
  • 4 行目からの Q 行には、ニコモバちゃんの落書きの情報が与えられる。このうち i 行目には、2 つの整数 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 行からなる。1 行目には、はじめの状態からゲームを始めた場合のニワンゴ君のスコアを出力し、2 行目から Q+1 行目までのうち i (1 ≦ i ≦ Q) 行目には、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