分数: 400 点
问题陈述
很快就完成了网络游戏的教程 ATChat,您决定访问一个特定的地方 N-1 碰巧在那里的玩家。这些 N 包括你在内的玩家都被编号了 1 通过 N,以及 友善 玩家的 玩家的 i is 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 玩家可以获得。
示例输入 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