分数: 400 点
问题陈述
高桥有 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