/ 
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
高橋君は Bucket Festival という大会に参加しようとしています。Bucket Festival ではバケツを使った様々な競技が行われますが、力に自信がある高橋君は「N 個のバケツ」という競技に参加することにしました。
「N 個のバケツ」のルールは以下の通りです。
- N 人 1 チームで参加する。チームのメンバーには 1～N の番号を割り振る。
- チームメンバー N 人は番号順に時計回りに円周上に並んで立つ。i (1 ≦ i ≦ N-1) 番のメンバーと i+1 番のメンバー、N 番のメンバーと 1 番のメンバーは隣り合うことになる。
- 隣り合った 2 人のメンバーの間には水の入った合計 N 個のバケツが置かれる。どのバケツにどれくらいの量の水を入れるかはチームで相談して決めることができる。ただし、水の量は全て整数値となっていなければならない。
- チームのメンバーは、自分の両側にある 2 つのバケツを持ち上げる。それぞれのバケツは 2 人のメンバーが協力して持ち上げることになる。N 個のバケツを全て持ち上げられれば成功となり、バケツに入った水の量の合計がスコアとなる。
高橋君はできるだけ高いスコアを取るためにはどのバケツにどれくらいの量の水を入れれば良いかを考えています。そのためにまず、チームメンバーの力を測りました。そして、i (1 ≦ i ≦ N) 番のメンバーの力が S_i であることが分かりました。力が p のメンバーは、自分が持つ 2 つのバケツの水の量の平均が p 以下であればバケツを持ち上げることができます。つまり、2 つのバケツの水の量をそれぞれ w,v とすると、(w+v)/2 ≦ p であれば持ち上げることができます。
高橋君のチームは即席のチームであるため、チームメンバーが変更になることがあります。メンバー変更は合計 Q 回行われ、i (1 ≦ i ≦ Q) 回目の変更では P_i 番のメンバーが変更となり、力が X_i であるメンバーが新たに P_i 番のメンバーとして加わります。それぞれのメンバー変更ごとに、変更後の時点で高橋君のチームが取ることのできるスコアの最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 ... S_N Q P_1 X_1 P_2 X_2 : P_Q X_Q
- 1 行目には、参加者の人数を表す整数 N (3 ≦ N ≦ 10^5) が与えられる。 100 点分のデータセットにおいて、N は偶数であることが保証される。
- 2 行目には、最初のチームメンバーの力を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 S_i (0 ≦ S_i ≦ 10^4) は、i 番のメンバーの力が S_i であることを表す。
- 3 行目には、チームメンバーの変更の回数を表す整数 Q (1 ≦ Q ≦ 10^5) が与えられる。
- 4 行目からの Q 行には、チームメンバーの変更の情報が与えられる。このうち i (1 ≦ i ≦ Q) 行目には、2 つの整数 P_i (1 ≦ P_i ≦ N), X_i (0 ≦ X_i ≦ 10^4) が与えられる。これは、i 回目のメンバー変更で P_i 番のメンバーが変更となり、力が X_i のメンバーが新たに加わることを表す。
追加点
この問題には追加点が設定されている。
- N が奇数であるデータセットにも正解した場合は、1 点が追加で与えられる。
なお、追加点を取らずに 100 点分のデータセットに正解した場合でもこの問題は正解として扱われる。
出力
出力は Q 行からなる。このうち i (1 ≦ i ≦ Q) 行目には、i 回目のメンバー変更の直後の時点で高橋君のチームが取ることのできるスコアの最大値を表す 1 つの整数を出力せよ。出力の末尾にも改行を入れること。
入力例1
4 2 2 2 2 2 1 3 3 0
出力例1
8 6
下図はそれぞれのメンバー変更の直後に最大スコアを取るためにどのバケツにどれくらいの量の水を入れれば良いかを表しています。丸はメンバーを表しており、丸の中の数はメンバーの力、丸の左上の数はメンバーの番号を表しています。バケツの絵の中に書かれた数は、バケツに入れる水の量を表しています。
入力例2
6 0 0 0 0 0 0 6 3 10000 4 10000 6 10000 2 10000 5 10000 1 10000
出力例2
0 20000 20000 20000 40000 60000