17749번 - Cake 서브태스크다국어

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

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

図 1: ケーキの例 (N = 5, A₁ = 2, A₂ = 8, A₃ = 1, A₄ = 10, A₅ = 9)

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

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

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

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

標準入力から以下の入力を読み込め．

• 1 行目には整数 N が書かれており，ケーキが N 個のピースに切り分けられていることを表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には整数 A_i が書かれており，i 番目のピースの大きさが A_i であ ることを表す．

標準出力に N 行出力せよ．i 行目 (1 ≤ i ≤ N) には，i 番目のピースを最初に取ったときに JOI くんが最 終的に取るピースの大きさの合計を表す 1 つの整数を出力せよ．

• 2 ≤ N ≤ 300 000．
• 1 ≤ A_i ≤ 1 000 000 000 (1 ≤ i ≤ N)．