← 返回题目列表

AtCoder · abc173_d

D. 围圈聊天

中文机器翻译题面 查看原题

分数: 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.

Figure

他们无法获得大于 7,所以答案是 7.


示例输入 2

7
1 1 1 1 1 1 1

示例输出 2

6