题目描述

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

首先，高桥可以自由选择一张卡片放在桌子上。然后，他可以根据需要重复以下操作多次（也可能是零次）：

• 设 $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$

输出

输出一个表示答案的整数。

样例输入 1

9 7
3 0 2 5 5 3 0 6 3

样例输出 1

11

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

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

然后，手中剩下的是第一张、第三张、第六张和第九张卡片，它们上面的整数总和为 $3 + 2 + 3 +3 = 11$。这是手中剩下的卡片上写着的整数的最小可能总和。

样例输入 2

1 10
4

样例输出 2

0

样例输入 3

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

样例输出 3

99