D - Takahashi's Solitaire

得分: $400$ 分

问题描述

Takahashi手里有 $N$ 张卡片。 对于 $i = 1, 2, \ldots, N$，第 $i$ 张卡片上有一个非负整数 $A_i$。

首先，Takahashi可以自由选择一张卡片从手里放到桌子上。 然后，他可以根据以下操作重复任意次数（可能为零）。

• 令 $X$ 为最后一张放在桌子上的卡片上的整数。如果他手里有卡片的整数为 $X$ 或者 $(X+1)\bmod M$，选择其中一张卡片放在桌子上。这里，$(X+1)\bmod M$ 表示将 $(X+1)$ 除以 $M$ 的余数。

请将写在他手中的牌上的整数的最小和打印出来。

约束

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i \lt M$
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出：

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

输出

输出答案。

9 7
3 0 2 5 5 3 0 6 3

11

假设他首先将第四张卡片（写着 $5$）放在桌子上，然后进行以下操作。

• 将第五张卡片（写着 $5$）放在桌子上。
• 将第八张卡片（写着 $6$）放在桌子上。
• 将第二张卡片（写着 $0$）放在桌子上。
• 将第七张卡片（写着 $0$）放在桌子上。

然后，剩下的是第一张、第三张、第六张和第九张卡片，上面的整数之和为 $3 + 2 + 3 +3 = 11$。 这是可能剩下来的卡片上的整数之和的最小值。

1 10
4

0

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

99