配点 : 100 点
問題文
1 如果要将其更改为输出最多为 N 它有多个 N 人们排队 坐在 M 椅子上。从左边开始 i 椅子 th 椅子 它被称为 i 。人 i 是一把椅子 请在 A_i 处坐下。
当一个人坐下时,距离该人左右最近的椅子的编号(如果没有, 0,M+1) L,R ,坐着的人的分数是 R - L 。
N 人们如何按顺序坐 N! 方法有很多,N 找出人们的分数的最大可能总和。
制約
- 1 \le N \le 2 \times 10^5
- N \le M \le 10^9
- 1 \le A_i \le M
- i \neq j 如果 A_i \neq A_j
部分点
这个问题有多个部分点。 如果正确答案是满足
- N \le 500 的数据集 如果满足 10 分被给予。
- N \le 3000 的数据集的答案是正确的,则附加 10 分被给予。
入力
输入将以以下形式通过标准输入给出。
N M A_1 A_2 \dots A_N
出力
打印答案。
入力例 1
3 10 3 7 10
出力例 1
28
例如,人们 如果您的座位顺序为 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 ,这是最大值。
入力例 2
5 20 3 10 11 14 17
出力例 2
73
入力例 3
10 1000000000 136909656 243332691 643531997 505919307 43553384 657638276 57213246 179732866 357373203 182482400
出力例 3
7649951260