AT_codefestival_2016_final_h Tokaido

[problemUrl]: https://atcoder.jp/contests/cf16-final/tasks/codefestival_2016_final_h $ N $ 個のマスが一列に並んでおり、左から順に $ 1～N $ の番号が付けられています。 すぬけくんとりんごさんはこのマス目を使って、以下のようなボードゲームで遊ぼうとしています。 1. はじめに、すぬけくんがすべてのマスに $ 1 $ つずつ整数を書く。 2. $ 2 $ 人のプレイヤーはそれぞれ $ 1 $ つずつ駒を用意し、すぬけくんは自分の駒をマス $ 1 $ に、りんごさんは自分の駒をマス $ 2 $ に置く。 3. 自分の駒が相手の駒より左にあるプレイヤーが駒を動かす。駒を動かす先は、今自分の駒が置かれているマスよりも右にあってかつ相手の駒が置かれていないマスでなければならない。 4. *3.* を繰り返し、これ以上駒を動かすことができなくなるとゲームは終了となる。 5. ゲーム終了時までに自分の駒を置いたことのあるマスに書かれた整数の合計が、それぞれのプレイヤーのスコアとなる。 すぬけくんはすでにマス $ i\ (1≦i≦N-1) $ に整数 $ A_i $ を書きましたが、まだマス $ N $ には整数を書いていません。 すぬけくんは $ M $ 個の整数 $ X_1,X_2,...,X_M $ それぞれについて、その数をマス $ N $ に書いてゲームを行ったときに「（すぬけくんのスコア）ー（りんごさんのスコア）」がいくらになるのかを計算することにしました。 ただし、それぞれのプレイヤーは「（自分のスコア）ー（相手のスコア）」を最大化するように駒を動かすものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_{N-1} $ $ M $ $ X_1 $ $ X_2 $ $ : $ $ X_M $

$ X_1\ \dots\ X_M $ の $ M $ 個の整数それぞれに対し、その数をマス $ N $ に書いたときの「（すぬけくんのスコア）ー（りんごさんのスコア）」を $ 1 $ 行にひとつずつ出力せよ。

### 制約 - $ 3≦N≦200,000 $ - $ 0≦A_i≦10^6 $ - $ A_i $ の総和は $ 10^6 $ 以下である。 - $ 1≦M≦200,000 $ - $ 0≦X_i≦10^9 $ ### 部分点 - $ M=1 $ を満たすデータセットに正解した場合は、$ 700 $ 点が与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 900 $ 点が与えられる。 ### Sample Explanation 1 ゲームは下図のように進行します。Sはすぬけくんの駒、Rはりんごさんの駒を表しています。 !\[\](https://atcoder.jp/img/code-festival-2016-final/0c38db3b7902579a8bc2d0798b8dda27.png) スコアは $ 2 $ 人とも $ 10 $ となり、「（すぬけくんのスコア）ー（りんごさんのスコア）」は $ 0 $ となります。