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).

서브태스크

힌트