AT_abc173_d [ABC173D] Chat in a Circle

你刚刚完成了在线游戏“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$ 个人的最大舒适度总和。

## 限制条件 - 所有输入均为整数。 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$ ## 样例解释 1 如果按 $4, 2, 1, 3$ 的顺序到达，并如图所示插入环中，舒适度总和为 $7$。  无法使舒适度总和超过 $7$，因此答案为 $7$。 由 ChatGPT 4.1 翻译