問題文

1 から N の番号がついた N 人の人が一列に並べられた M 個の椅子に座ります。左から i 番目の椅子を椅子 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 点が与えられる。

入力例 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