Increasing by Modulo

给出 $n,m$，以及 $m$ 个数 $a_1,a_2,\ldots,a_n$。 每次选一个数 $k$ 及 $k$ 个数 $1\leq b_1\lt b_2\lt\ldots\lt b_k\leq n$，并将所有 $a_{b_i}$ 变成 $(a_{b_i}+1)\bmod m$，求最少操作数，使 $a$ 数组不下降。

Toad Zitz has an array of integers, each integer is between $ 0 $ and $ m-1 $ inclusive. The integers are $ a_1, a_2, \ldots, a_n $ . In one operation Zitz can choose an integer $ k $ and $ k $ indices $ i_1, i_2, \ldots, i_k $ such that $ 1 \leq i_1 < i_2 < \ldots < i_k \leq n $ . He should then change $ a_{i_j} $ to $ ((a_{i_j}+1) \bmod m) $ for each chosen integer $ i_j $ . The integer $ m $ is fixed for all operations and indices. Here $ x \bmod y $ denotes the remainder of the division of $ x $ by $ y $ . Zitz wants to make his array non-decreasing with the minimum number of such operations. Find this minimum number of operations.

The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 300\,000 $ ) — the number of integers in the array and the parameter $ m $ . The next line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i < m $ ) — the given array.

Output one integer: the minimum number of described operations Zitz needs to make his array non-decreasing. If no operations required, print $ 0 $ . It is easy to see that with enough operations Zitz can always make his array non-decreasing.

5 3
0 0 0 1 2

0

5 7
0 6 1 3 2

1

In the first example, the array is already non-decreasing, so the answer is $ 0 $ . In the second example, you can choose $ k=2 $ , $ i_1 = 2 $ , $ i_2 = 5 $ , the array becomes $ [0,0,1,3,3] $ . It is non-decreasing, so the answer is $ 1 $ .