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$ 个人的最大舒适度总和。

输入输出样例 #1

输入 #1

4
2 2 1 3

输出 #1

7

输入输出样例 #2

输入 #2

7
1 1 1 1 1 1 1

输出 #2

6

说明/提示

限制条件

• 所有输入均为整数。
• $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 翻译