AT_npcapc_2024_f Train Seats

$ 1 $ から $ N $ の番号がついた $ N $ 人の人が一列に並べられた $ M $ 個の椅子に座ります。左から $ i $ 番目の椅子を椅子 $ i $ と呼びます。人 $ i $ は椅子 $ A_i $ に座ります。 ある人が座った時に、その人の左右それぞれで最も近い座っている人のいる椅子の番号（それぞれない場合は $ 0,M+1 $ ）を $ L,R $ としたとき、座った人のスコアを $ R - L $ とします。 $ N $ 人が順番に座る方法は $ N! $ 通りありますが、 $ N $ 人のスコアの総和としてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力せよ。

### 部分点 この問題には複数の部分点が設定されている。 - $ N \le 500 $ を満たすデータセットに正解した場合 $ 10 $ 点が与えられる。 - $ N \le 3000 $ を満たすデータセットに正解した場合追加で $ 10 $ 点が与えられる。 ### Sample Explanation 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 $ となり、この時が最大です。 ### Constraints - $ 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 $