有 $N$ 个人，编号为 $1$ 到 $N$，坐在排成一行的 $M$ 把椅子上。从左往右数第 $i$ 个位置的椅子称为椅子 $i$。第 $i$ 个人坐在椅子 $A_i$ 上。

当一个人坐下时，设 $L$ 和 $R$ 分别为该人左侧和右侧最近的已占用椅子的编号（如果左侧没有已占用的椅子，则 $L = 0$；如果右侧没有已占用的椅子，则 $R = M + 1$）。该人的得分为 $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 \ M$ $A_1 \ A_2 \ \dots \ A_N$

输出格式

输出答案。

样例

样例输入 1

3 10
3 7 10

样例输出 1

28

样例输入 2

5 20
3 10 11 14 17

样例输出 2

73

样例输入 3

10 1000000000
136909656 243332691 356357841 368234985 439239485 593847562 612384756 723847562 847562341 182482400

样例输出 3

7649951260

说明

对于第一个样例： 例如，如果人们按第 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$，这是最大值。