200772: [AtCoder]ARC077 E - guruguru

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

Snuke is buying a lamp. The light of the lamp can be adjusted to $m$ levels of brightness, represented by integers from $1$ through $m$, by the two buttons on the remote control.

The first button is a "forward" button. When this button is pressed, the brightness level is increased by $1$, except when the brightness level is $m$, in which case the brightness level becomes $1$.

The second button is a "favorite" button. When this button is pressed, the brightness level becomes the favorite brightness level $x$, which is set when the lamp is purchased.

Snuke is thinking of setting the favorite brightness level $x$ so that he can efficiently adjust the brightness. He is planning to change the brightness $n-1$ times. In the $i$-th change, the brightness level is changed from $a_i$ to $a_{i+1}$. The initial brightness level is $a_1$. Find the number of times Snuke needs to press the buttons when $x$ is set to minimize this number.

Constraints

  • $2 \leq n,m \leq 10^5$
  • $1 \leq a_i\leq m$
  • $a_i \neq a_{i+1}$
  • $n$, $m$ and $a_i$ are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum number of times Snuke needs to press the buttons.


Sample Input 1

4 6
1 5 1 4

Sample Output 1

5

When the favorite brightness level is set to $1$, $2$, $3$, $4$, $5$ and $6$, Snuke needs to press the buttons $8$, $9$, $7$, $5$, $6$ and $9$ times, respectively. Thus, Snuke should set the favorite brightness level to $4$. In this case, the brightness is adjusted as follows:

  • In the first change, press the favorite button once, then press the forward button once.
  • In the second change, press the forward button twice.
  • In the third change, press the favorite button once.

Sample Input 2

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

Sample Output 2

45

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: