题目描述

在在线游戏_ATChat_的教程结束后不久，你决定和另外$N-1$个玩家一起去一个特定的地方。这$N$个玩家，包括你自己，编号为$1$到$N$，并且玩家$i$的友好程度为$A_i$。

这$N$个玩家将按某种顺序一个接一个地到达这个地方。为了确保没有人迷路，你制定了以下规则：已经到达那里的玩家应该形成一个圆圈，而刚刚到达那里的玩家应该在圆圈的某个位置插入。

当每个玩家（除了第一个到达的玩家）到达时，该玩家会获得舒适度，该舒适度等于顺时针相邻玩家和逆时针相邻玩家友好程度中较小的那个。第一个到达的玩家的舒适度为$0$。

通过在最佳的到达顺序和圆圈中的位置选择，$N$个玩家可以获得的最大总舒适度是多少？

约束条件

• 输入中的所有值都是整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$

输入

输入以以下格式从标准输入给出：

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

输出

打印最大总舒适度。

示例输入1

4
2 2 1 3

示例输出1

7

通过按照玩家$4, 2, 1, 3$的顺序到达，并按照图中所示在圆圈中插入，他们可以获得总舒适度为$7$。

他们无法获得超过$7$的总舒适度，因此答案是$7$。

示例输入2

7
1 1 1 1 1 1 1

示例输出2

6