分数: 700 点
问题陈述
Snuke 正在买一盏灯。 灯的亮度可以调节 m 亮度级别,由整数表示 1 通过 m,通过遥控器上的两个按钮。
第一个按钮是“前进”按钮。按下此按钮时,亮度级别会增加 1,除非亮度级别为 m,在这种情况下亮度级别变为 1.
第二个按钮是“收藏夹”按钮。按下此按钮时,亮度级别变为最喜欢的亮度级别 x,在购买灯泡时设置。
Snuke 正在考虑设置最喜欢的亮度级别 x 以便他可以高效地调节亮度。 他正计划改变亮度 n-1 次。 i第次更改,亮度级别从 a_i to a_{i+1}。初始亮度级别为 a_1。 求 Snuke 需要按下按钮的次数 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
输出
打印 Snuke 需要按下按钮的最少次数。
示例输入 1
4 6 1 5 1 4
示例输出 1
5
当喜爱的亮度级别设置为 1, 2, 3, 4, 5 和 6,Snuke需要按下按钮 分别为 8, 9, 7, 5, 6 和 9 次。 因此,Snuke 应该将最喜欢的亮度级别设置为 4。 在这种情况下,亮度调整如下:
- 在第一次更改时,按一次收藏按钮,然后按一次前进按钮。
- 在第二次更改时,按前进按钮两次。
- 在第三次更改中,按一次收藏按钮。
示例输入 2
10 10 10 9 8 7 6 5 4 3 2 1
示例输出 2
45