配点 : $700$ 点

問題文

snuke 君は明るさを $m$ 段階に切り替えられる照明を買いに来ました。 この照明の 明るさは $1$ 以上 $m$ 以下の整数で表され、 リモコンに付いた $2$ 種類のボタンで明るさを切り替えます。

$1$ つめのボタンは「順送り」ボタンで、 明るさを $1$ 増やすことができます。ただし、ボタンを押す前の明るさが最大の $m$ である場合には、 明るさは $1$ になります。

$2$ つめのボタンは「お気に入り」ボタンで、 購入時に決めたお気に入りの明るさ $x$ に切り替えることが出来ます。

snuke 君はお気に入りの明るさ $x$ を、できるだけ効率的に明るさが切り替えられるように設定しようと考えました。 snuke 君は今後 $n-1$ 回明るさを切り替える予定で、$i$ 回目には明るさ $a_i$ から 明るさ $a_{i+1}$ に切り替えようと計画しています。 最初、明るさは $a_1$ です。 ボタンを押す回数の合計が最小になるようにお気に入りの明るさ $x$ を決めた時の ボタンを押す回数を求めて下さい。

制約

• $2 \leq n,m \leq 10^5$
• $1 \leq a_i\leq m$
• $a_i \neq a_{i+1}$
• $n,m,a_i$ は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$n$ $m$

$a_1$ $a_2$ … $a_n$

出力

ボタンを押す回数の合計の最小値を出力せよ。

4 6
1 5 1 4

5

お気に入りの明るさを $1,2,3,4,5,6$ のそれぞれに設定したときのボタンを押す最小回数はそれぞれ $8,9,7,5,6,9$ 回です。 よって、お気に入りの明るさを $4$ に設定したときにボタンを押す回数の合計を最小に出来ます。 お気に入りの明るさを $4$ に設定したときの切り替え方は以下のとおりです。

• $1$ 回目には、お気に入りボタンを $1$ 回押した後、順送りボタンを $1$ 回押します。
• $2$ 回目には、順送りボタンを $2$ 回押します。
• $3$ 回目には、お気に入りボタンを $1$ 回押します。

10 10
10 9 8 7 6 5 4 3 2 1

45