← 返回题目列表

AtCoder · arc077_c

E. 大师

中文机器翻译题面 查看原题

分数: 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