CF1168A Increasing by Modulo

蟾蜍 Zitz 有一个整数数组，每个整数都在 $0$ 到 $m-1$ 之间（包含 $0$ 和 $m-1$）。这些整数为 $a_1, a_2, \ldots, a_n$。 每次操作，Zitz 可以选择一个整数 $k$ 和 $k$ 个下标 $i_1, i_2, \ldots, i_k$，满足 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$。然后，他将每个被选中的 $a_{i_j}$ 替换为 $((a_{i_j}+1) \bmod m)$。整数 $m$ 在所有操作和下标中都是固定的。 这里 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。 Zitz 想用最少的操作次数，使他的数组变为非递减数组。请你求出所需的最小操作次数。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300\,000$），分别表示数组的长度和参数 $m$。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i < m$），表示给定的数组。

输出一个整数，表示将数组变为非递减数组所需的最小操作次数。如果不需要操作，输出 $0$。 可以证明，通过足够多的操作，总能将数组变为非递减数组。

在第一个样例中，数组已经是非递减的，所以答案是 $0$。 在第二个样例中，你可以选择 $k=2$，$i_1=2$，$i_2=5$，数组变为 $[0,0,1,3,3]$。此时数组是非递减的，所以答案是 $1$。 由 ChatGPT 4.1 翻译