配点: $400$ 点

問題文

あなたはオンラインゲーム「ATChat」のチュートリアルを終え、その場に居合わせたプレイヤー $N$ 人で早速とある場所を訪ねることにしました。この $N$ 人には $1$ から $N$ の番号が振られており、人 $i\ (1 \leq i \leq N)$ の フレンドリーさ は $A_i$ です。

訪ねる際、$N$ 人は好きな順番で $1$ 人ずつ到着します。あなたたちは迷子にならないために、既に到着した人たちで環状に並び、新たに到着した人は好きな位置に割り込んで加わるというルールを決めました。

最初に到着した人以外の各人は、割り込んだ位置から到着した時点で「時計回りで最も近い人」と「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい 心地よさ を感じます。最初に到着した人の心地よさは $0$ です。

$N$ 人が到着する順番や割り込む位置を適切に決めたとき、$N$ 人の心地よさの合計の最大値はいくらになるでしょう？

制約

• 入力はすべて整数
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

出力

$N$ 人の心地よさの合計の最大値を出力せよ。

4
2 2 1 3

7

人 $4, 2, 1, 3$ がこの順に到着し、図のように輪に割り込むことで、心地よさの合計は $7$ になります。

心地よさの合計を $7$ より大きくすることはできないので、$7$ が答えになります。

7
1 1 1 1 1 1 1

6