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 \lt i_2 \lt \ldots \lt 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.

蟾蜍 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 \lt i_2 \lt \ldots \lt i_k \leq n$。然后，他对每个选定的下标 $i_j$ 将 $a_{i_j}$ 修改为 $((a_{i_j}+1) \bmod m)$。整数 $m$ 在所有操作及下标选择中保持不变。

此处 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。

Zitz 希望以最少的操作次数使该数组变为非递减序列。请找出这个最小操作次数。

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 \lt m$) — the given array.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300\,000$）—— 分别表示数组中整数的个数和参数 $m$。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \lt m$）—— 给定的数组。

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.

输出一个整数：Zitz 使其数组变为非递减序列所需的最少操作次数。若无需任何操作，则输出 $0$。

显然，通过足够多次的操作，Zitz 总能将其数组变为非递减序列。

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

在第一个例子中，数组已经是非递减的，因此答案为 $0$。

在第二个例子中，你可以选择 $k=2$、$i_1 = 2$、$i_2 = 5$，此时数组变为 $[0,0,1,3,3]$。该数组是非递减的，因此答案为 $1$。