题目描述

snuke 君来买了一盏可以调节 $m$ 个亮度级别的灯。这盏灯的亮度用 $1$ 到 $m$ 之间的整数表示，可以通过遥控器上的两种按钮进行切换。

第一种按钮是“顺序切换”按钮，按下时亮度增加 $1$。但如果当前亮度是最大值 $m$，再按下时亮度会回到 $1$。

第二种按钮是“最爱”按钮，可将亮度直接切换到购买时设定的最爱亮度 $x$。

snuke 君希望将最爱亮度 $x$ 设置成能够尽量高效地切换亮度的数。他计划在之后的 $n-1$ 次切换亮度，第 $i$ 次将亮度从 $a_i$ 切换到 $a_{i+1}$。起始时亮度为 $a_1$。请帮他求出如果最爱亮度 $x$ 设为最优值时，所有需要的按钮点击次数的最小值。

输入格式

输入按以下格式从标准输入给出。

$n\ m\ a_1\ a_2\ \cdots\ a_n$

输出格式

输出最小按钮按下的总次数。

样例 1

输入

4 6
1 5 1 4

输出

5

样例 2

输入

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$ 均为整数。

样例解释 1

当最爱亮度设置为 $1, 2, 3, 4, 5, 6$ 时，最少按钮按下次数分别为 $8, 9, 7, 5, 6, 9$。所以，当最爱亮度设为 $4$ 时，总按键次数最少。
最爱亮度为 $4$ 时的切换方式如下：

• 第 $1$ 次，先按一次最爱按钮，再按一次顺序切换按钮。
• 第 $2$ 次，按两次顺序切换按钮。
• 第 $3$ 次，按一次最爱按钮。

由 ChatGPT 5 翻译