圆桌聊天

题目描述

你完成了在线游戏「ATChat」的教程,决定和在场的 $N$ 名玩家一起去拜访某处。这 $N$ 人被编号为 $1$ 到 $N$,人 $i\ (1 \leq i \leq N)$ 的友好度为 $A_i$。

拜访时,$N$ 人按任意顺序一个个到达。为了不迷路,你们定下规则:已经到达的人围成一个环,新到达的人可以任意插到某个位置加入。

除第一个到达的人之外,每个人在插入时,会感受到与「顺时针方向最近的人」和「逆时针方向最近的人」的友好度中较小者相等的舒适度。第一个到达的人的舒适度为 $0$。

当 $N$ 人的到达顺序和插入位置都恰当地决定时,$N$ 人的舒适度之和的最大值是多少?

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• 输入均为整数
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$