AT_dwango2015_finals_4 コインの取り合い

[problemUrl]: https://atcoder.jp/contests/dwango2015-finals/tasks/dwango2015_finals_4 ニワンゴ君とニコモバちゃんはコインを使ったゲームをしています。 はじめ $ 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+1 $ 行からなる。$ 1 $ 行目には、はじめの状態からゲームを始めた場合のニワンゴ君のスコアを出力し、$ 2 $ 行目から $ Q+1 $ 行目までのうち $ i\ (1\ ≦\ i\ ≦\ Q) $ 行目には、$ i $ 回目の落書きの直後にゲームを始めた場合のニワンゴ君のスコアを出力せよ。出力の末尾にも改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ Q\ =\ 0 $ を満たすデータセット $ 1 $ に正解した場合は、$ 10 $ 点が与えられる。 - $ S_i\ ≦\ 25 $ を満たすデータセット $ 2 $ に正解した場合は、上記とは別に $ 80 $ 点が与えられる。 - 全てのテストケースに正解した場合は、上記とは別に $ 90 $ 点が与えられる。 ### Sample Explanation 1 この例では、$ 4 $ 枚のコインがあり、それらの価値は左から順に $ 1,2,3,4 $ です。はじめ、コインの上の面は「表裏表裏」となっています。この状態からゲームを始めると、 - ニワンゴ君がコイン $ 2 $ をひっくり返す → ニコモバちゃんがコイン $ 3 $ をひっくり返す → ニワンゴ君がコイン $ 4 $ をひっくり返す となり、最終状態のコインの上の面は「表表裏表」なので、ニワンゴ君のスコアは $ 7 $ 点となります。 また、この例では $ 1 $ 個のクエリがあります。クエリによってコイン $ 4 $ の価値が $ 1 $ に下がります。この状態からゲームを始めると、 - ニワンゴ君がコイン $ 2 $ をひっくり返す → ニコモバちゃんがコイン $ 2 $ をひっくり返す → ニワンゴ君がコイン $ 4 $ をひっくり返す となり、最終状態のコインの上の面は「表裏表表」なので、ニワンゴ君のスコアは $ 5 $ 点となります。