D - 在圆形中聊天

分数：400分

问题描述

在线游戏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$

输出

输出$N$个玩家能够获得的最大总舒适度。

4
2 2 1 3

7

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

他们无法获得大于$7$的总舒适度，所以答案是$7$。

7
1 1 1 1 1 1 1

6