CF1168A Increasing by Modulo

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.

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 $ .