#Q7888. 2268 [Noip模拟题]送分题

2268 [Noip模拟题]送分题

题目描述

你有一个可以调节明暗度的灯泡。这个灯泡有m个明暗度,分别为1,2,3...m。灯泡有一个遥控器。你每按一次遥控 器,假设灯泡当前亮度为x,按一次以后就变成了x+1,如果x为m,则按一次以后变成1。每个灯泡在设计时都有一 个按钮,且有一个舒适值k,你可以按一次按钮,无论你现在的亮度是多少,你的亮度都会变成k。按一次按钮或按 一次遥控器都算是操作一次,现在给你一个序列a1~an,一开始你的亮度是a1,然后你要将亮度调到a2,再到a3, 再到a4,再到a5...最后到an,完成这个亮度变化的过程会得到一个最小的操作次数T,现在问你如何指定舒适值( 舒适值指定之后不能改变),使得T最小。

输入

第一行两个整数,表示n,m。 第二行n个整数,第i个整数表示ai。 2 ≤n,m≤1000000, 1≤ai≤m, ai≠ai+1

输出

输出一个整数,表示T的最小值。

样例

4 6
1 5 1 4	
5