Toad Zitz 有一个整数数组,每个整数都在 $$$0$$$ 和 $$$m-1$$$ 之间(含)。整数为$$$a_1、a_2、\ldots、a_n$$$。
在一次操作中,Zitz 可以选择一个整数 $$$k$$$ 和 $$$k$$$ 索引 $$$i_1, i_2, \ldots, i_k$$$,使得 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$。然后,他应该将每个选定的整数 $$$i_j$$$ 更改为 $$$((a_{i_j}+1) \bmod m)$$$。对于所有操作和索引,整数 $$$m$$$ 都是固定的。
这里 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。
Zitz 希望通过最少数量的此类操作使他的数组不减。求这个最小操作数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 300\,000$$$) - 数组和参数 $$$m$$$ 中的整数个数。
下一行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < m$$$) — 给定数组。
输出
输出一个整数:Zitz 需要使他的数组不减的最少描述操作数。如果不需要任何操作,则打印$$$0$$$。
很容易看出,通过足够的操作,Zitz 总是可以使他的数组不减。
示例
输入 #1
5 3 0 0 0 1 2
输出 #1
0
输入 #2
5 7 0 6 1 3 2
输出 #2
1
注意
在第一个示例中,数组已经是非递减的,因此答案是 $$$0$$$。
在第二个示例中,可以选择$$$k=2$$$、$$$i_1 = 2$$$、$$$i_2 = 5$$$,数组变为$$$[0,0,1,3,3]$$$。它是非递减的,所以答案是 $$$1$$$。