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