AT_npcapc_2024_f Train Seats

有 $N$ 个人，编号从 $1$ 到 $N$，他们被安排坐在 $M$ 把椅子上，这些椅子从左到右编号为 $1$ 到 $M$。每个人 $i$ 会坐在第 $A_i$ 号椅子上。 当某个人坐下时，记该人左右两侧最近的已有人坐的椅子的编号分别为 $L$ 和 $R$（若不存在则 $L=0$，$R=M+1$），该人的得分为 $R-L$。 $N$ 个人的入座顺序共有 $N!$ 种可能，请你求出所有顺序中 $N$ 个人得分总和的最大值。

输入为一行，通过标准输入给出。 > $N\ M\ A_1\ A_2\ \dots\ A_N$

输出一个整数，表示答案。

## 部分分 本题设有多组部分分。 - 对于满足 $N \leq 500$ 的数据集，答对可得 $10$ 分。 - 对于满足 $N \leq 3000$ 的数据集，答对可再得 $10$ 分。 ## 样例解释 1 例如，若入座顺序为“人 $3$，人 $1$，人 $2$”，则各人得分如下： - 人 $3$ 入座时，$L=0$，$R=11$，得分为 $11-0=11$。 - 人 $1$ 入座时，$L=0$，$R=10$，得分为 $10-0=10$。 - 人 $2$ 入座时，$L=3$，$R=10$，得分为 $10-3=7$。 因此总得分为 $11+10+7=28$，这是最大值。 ## 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $N \leq M \leq 10^9$ - $1 \leq A_i \leq M$ - 若 $i \neq j$，则 $A_i \neq A_j$。 由 ChatGPT 5 翻译