← 返回题目列表

AtCoder · npcapc_2024_f

F. 火车座椅

中文机器翻译题面 查看原题

配点 : 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