問題文

JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんはケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので 2 人でケーキを分けることになった．

ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを N 個のピースに切り分け，ピースに 1 から N まで反時計回りに番号をつけた．つまり，1 \leqq i \leqq N に対し，i 番目のピースは i - 1 番目と i + 1 番目のピースと隣接している (ただし 0 番目は N 番目，N + 1 番目は 1 番目とみなす) ．i 番目のピースの大きさは A_{i} だったが，切り方がとても下手だったので A_{i} はすべて異なる値になった．

図 1: ケーキの例 (N = 5，A_{1} = 2，A_{2} = 8，A_{3} = 1，A_{4} = 10，A_{5} = 9)

この N 個を JOI くんと IOI ちゃんで分けることにした．分け方は次のようにすることにした：

• まず JOI くんが N 個のうちの 1 つを選んで取る．
• その後，IOI ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを 1 つずつ取っていく．ただし，(2 人はケーキを崩さないように取るのが下手なので) 両隣のピースのうち少なくとも一方が既に取られているようなピースしか取ることができず，取れるピースが複数あるときはそのうち最も大きいものを選んで取る．

JOI くんは，各ピースについて，そのピースを最初に取ったとき自分が最終的に取るピースの大きさの合計がいくらになるか知りたくなった．

課題

ケーキのピースの数 N と，N 個のピースの大きさの情報が与えられたとき，各ピースについて，そのピースを最初に取ったときに JOI くんが最終的に取るピースの大きさの合計を求めるプログラムを作成せよ．

制約

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 300\,000．
• 1 \leqq A_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．

小課題

小課題 1 [10 点]

• N \leqq 5\,000 を満たす．

小課題 2 [90 点]

追加の制限はない．

入出力例

入力例 1

5
2
8
1
10
9

出力例 1

13
18
12
13
12

この例は問題文中の図の例に対応している．

たとえば 1 番目のピースを最初に取ったとする．このとき，

• 残っているピースのうち「両隣のピースのうち少なくとも一方が既に取られている」ピースは 2 番目と 5 番目で，5 番目のピースのほうが大きいので次は 5 番目のピースが取られる．
• 同様に，次は 2 番目と 4 番目のピースを比べて 4 番目のほうが大きいので 4 番目のピースが取られる．
• 次は 2 番目と 3 番目のピースを比べて 2 番目のほうが大きいので 2 番目のピースが取られる．
• 最後は 3 番目のピースしか残っていないので 3 番目のピースが取られる．

つまりピースの取られる順は

1 番目 (2) \to 5 番目 (9) \to 4 番目 (10) \to 2 番目 (8) \to 3 番目 (1) (括弧の中はピースの大きさ)

となり，JOI くんが取るピースは 1 番目，4 番目，3 番目のピースで，その大きさの合計は 13 なので 1 行目には 13 を出力する．1 番目以外のピースを最初に取った場合も同様に求める．