시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 2 2 2 100.000%

문제

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

예제 입력 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) → 5 番目 (9) → 4 番目 (10) → 2 番目 (8) → 3 番目 (1)

(括弧の中はピースの大きさ)

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