/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
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 を決めた時の ボタンを押す回数を求めて下さい。
制約
- 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
出力
ボタンを押す回数の合計の最小値を出力せよ。
入力例 1
4 6 1 5 1 4
出力例 1
5
お気に入りの明るさを 1,2,3,4,5,6 のそれぞれに設定したときのボタンを押す最小回数はそれぞれ 8,9,7,5,6,9 回です。 よって、お気に入りの明るさを 4 に設定したときにボタンを押す回数の合計を最小に出来ます。 お気に入りの明るさを 4 に設定したときの切り替え方は以下のとおりです。
- 1 回目には、お気に入りボタンを 1 回押した後、順送りボタンを 1 回押します。
- 2 回目には、順送りボタンを 2 回押します。
- 3 回目には、お気に入りボタンを 1 回押します。
入力例 2
10 10 10 9 8 7 6 5 4 3 2 1
出力例 2
45
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