题目描述

给定 $n$ 个数的数组 $a[]$，每轮调整可以把任意多个不同下标的元素 $a_i$ 调整成 $(a_i + 1) \bmod M$。

问最少经过多少轮可以把 $a[]$ 调整成非递减序列。

注意：

1. $x \bmod y$ 表示 $x$ 对 $y$ 取余，比如 $19 \bmod 5 = 4$；
2. 我们称一个（下标从 1 开始）序列 $s[]$ 非递减，当且仅当 $s[]$ 对于任意 $1<i<=n$ 满足 $s_{i-1} <= s_i$。

输入格式

第一行两个数：$n$ 和 $M$。 接下来一行 $n$ 个数，分别表示 $a_1, a_2, ..., a_n$。

输出格式

输出仅一个数，表示把 $a[]$ 调整成非递减序列需要的最少轮次。

样例

样例输入1

5 10
5 4 3 2 1

样例输出 1

4

样例输入 2

4 10
7 8 3 2

样例输出 2

3

提示

样例说明：

对于样例 2，经过一轮调整后可以变成：[8, 8, 3, 2]； 经过第二轮调整后可以变成：[9,9,3,3]； 再经过一轮调整，即可变成非递减序列：[0,0,3,3]。

数据范围：

• 对于 $30\%$ 的数据，满足 $M < 1000$；
• 对于另外 $20\%$ 的数据，满足 $a_i < \frac{M}{2}$；
• 对于 $100\%$ 的数据，满足 $1 <= N <= 10^5$，满足 $0 <= a_i < M <= 10^8$。

---