AT_abc173_d [ABC173D] Chat in a Circle

[problemUrl]: https://atcoder.jp/contests/abc173/tasks/abc173_d あなたはオンラインゲーム「ATChat」のチュートリアルを終え、その場に居合わせたプレイヤー $ N $ 人で早速とある場所を訪ねることにしました。この $ N $ 人には $ 1 $ から $ N $ の番号が振られており、人 $ i\ (1\ \leq\ i\ \leq\ N) $ の **フレンドリーさ** は $ A_i $ です。 訪ねる際、$ N $ 人は好きな順番で $ 1 $ 人ずつ到着します。あなたたちは迷子にならないために、既に到着した人たちで環状に並び、新たに到着した人は好きな位置に割り込んで加わるというルールを決めました。 最初に到着した人以外の各人は、割り込んだ位置から到着した時点で「時計回りで最も近い人」と「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい **心地よさ** を感じます。最初に到着した人の心地よさは $ 0 $ です。 $ N $ 人が到着する順番や割り込む位置を適切に決めたとき、$ N $ 人の心地よさの合計の最大値はいくらになるでしょう？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

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

### 制約 - 入力はすべて整数 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ ### Sample Explanation 1 人 $ 4,\ 2,\ 1,\ 3 $ がこの順に到着し、図のように輪に割り込むことで、心地よさの合計は $ 7 $ になります。 !\[図\](https://img.atcoder.jp/ghi/766a260a0019ea93e86e0588cc4db868.png) 心地よさの合計を $ 7 $ より大きくすることはできないので、$ 7 $ が答えになります。