题目描述

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$ を決めた時の ボタンを押す回数を求めて下さい。

输入格式

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

$n$ $m$ $a_1$ $a_2$ … $a_n$

输出格式

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

题目大意

题目大意:
一盏灯上有一个理想开关用于调到理想亮度 $X$ , 灯的亮度由 $1$ 到 $M$ , 但是在购买这盏灯时, 理想开关的数值就确定好了. $snuke$ 会进行 $N-1$ 次操作, 第 $i$ 次操作将灯的亮度由 $A_i$ 调到 $A_{i+1}$ .灯的亮度有两种调节方式, 一种是每次将亮度 $+1$ , 若当前亮度是 $M$ , 那么 $M+1$ 后的亮度为 $1$ , 另一种是直接将亮度调到理想亮度 $X$ . 希望确定 $X$ , 使得总的调节次数最少, 并输出这个最少调节数.

感谢@凌幽 提供的翻译

4 6
1 5 1 4

5

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

45

提示

制約

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

Sample Explanation 1

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