← 返回题目列表

Codeforces · 1168/A

A. 按模增加

中文机器翻译题面 查看原题

Toad 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 < i_2 < \ldots < i_k \leq n$$$。然后,他应该将每个选定的整数 $$$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$$$) — 给定数组。

输出

输出一个整数:Zitz 需要使他的数组不减的最少描述操作数。如果不需要任何操作,则打印$$$0$$$。

很容易看出,通过足够的操作,Zitz 总是可以使他的数组不减。

示例

输入 #1

5 3
0 0 0 1 2

输出 #1

0

输入 #2

5 7
0 6 1 3 2

输出 #2

1

注意

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

在第二个示例中,可以选择$$$k=2$$$、$$$i_1 = 2$$$、$$$i_2 = 5$$$,数组变为$$$[0,0,1,3,3]$$$。它是非递减的,所以答案是 $$$1$$$。