Cake
시간 제한1.5초메모리 제한256 MB
크기가 모두 다른 원형 케이크에서 남은 조각을 가져가는 규칙이 정해져 있을 때, 각 조각을 처음 선택한 경우 JOI가 최종적으로 가져가는 조각 크기의 합을 구한다.
문제
JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんは ケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので 2 人でケーキを分けることになった．
ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを N 個のピースに切り分け，ピースに 1 から N まで反時計回りに番号をつけた．つまり，1 ≤ i ≤ N に対し，i 番目のピースは i − 1 番目と i + 1 番 目のピースと隣接している (ただし 0 番目は N 番目，N + 1 番目は 1 番目とみなす) ．i 番目のピースの大 きさは Ai だったが，切り方がとても下手だったので Ai はすべて異なる値になった．
図 1: ケーキの例 (N = 5, A1 = 2, A2 = 8, A3 = 1, A4 = 10, A5 = 9)
この N 個を JOI くんと IOI ちゃんで分けることにした．分け方は次のようにすることにした：
- まず JOI くんが N 個のうちの 1 つを選んで取る．
- その後，IOI ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを 1 つずつ取っていく． ただし， (2 人はケーキを崩さないように取るのが下手なので) 両隣のピースのうち少なくとも一方が 既に取られているようなピースしか取ることができず，取れるピースが複数あるときはそのうち最も 大きいものを選んで取る．
JOI くんは，各ピースについて，そのピースを最初に取ったとき自分が最終的に取るピースの大きさの 合計がいくらになるか知りたくなった．
ケーキのピースの数 N と，N 個のピースの大きさの情報が与えられたとき，各ピースについて，そのピー スを最初に取ったときに JOI くんが最終的に取るピースの大きさの合計を求めるプログラムを作成せよ．
입력
標準入力から以下の入力を読み込め．
- 1 行目には整数 N が書かれており，ケーキが N 個のピースに切り分けられていることを表す．
- 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には整数 Ai が書かれており，i 番目のピースの大きさが Ai であ ることを表す．
출력
標準出力に N 行出力せよ．i 行目 (1 ≤ i ≤ N) には，i 番目のピースを最初に取ったときに JOI くんが最 終的に取るピースの大きさの合計を表す 1 つの整数を出力せよ．
제한
- 2 ≤ N ≤ 300 000．
- 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N)．