Increasing by Modulo

2000ms

262144K

Description:

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.

Input:

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:

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.

Sample Input:

5 3
0 0 0 1 2

Sample Output:

Sample Input:

5 7
0 6 1 3 2

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF1168A