题目描述

あなたはオンラインゲーム「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$ 人の心地よさの合計の最大値を出力せよ。

题目大意

完成在线游戏 $ATchat$ 的教程后，你很快决定与 $n-1$ 个碰巧也在那里的玩家一起访问一个特定的地方。这 $n$ 个玩家，包括你在内，从 $1$ 到 $n$ 编号，玩家的友好度为 $A_i$。$n$ 个玩家将按照一定的顺序一个一个到达。为了确保没有人迷路，你设置了以下规则：已经到达那里的玩家应该围成一圈，而刚刚到达那里的玩家应该在某个位置切入圈子。第一个到达那里的玩家得到 $0$ 的舒适度。当除第一个到达的玩家之外的每个玩家到达该地点时，玩家获得的舒适度等于顺时针相邻玩家的友好度和逆时针相邻玩家的友好度中的较小那个数。通过最佳选择到达顺序和切入圆圈中的位置，$n$ 个玩家可以获得的最大总舒适度是多少？

4
2 2 1 3

7

7
1 1 1 1 1 1 1

6

提示

制約

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

Sample Explanation 1

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