AT_arc169_d.[ARC169D] Add to Make a Permutation

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。$A$ 的每个元素都是 $0$ 到 $N-1$ 之间的整数。

你可以进行如下操作任意次（包括 $0$ 次）：

• 从 $A$ 中恰好选出 $M$ 个元素，将选中的每个元素的值加 $1$。如果加 $1$ 后某个元素的值变成了 $N$，则将其值变为 $0$。

你的目标是将 $A$ 变成 $ (0,1,\cdots,N-1) $ 的一个排列。请判断目标是否可以达成，如果可以，输出所需的最小操作次数；否则输出 $-1$。

输入通过标准输入给出，格式如下：

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$

如果无法达成目标，输出 $-1$。如果可以，输出所需的最小操作次数。

限制条件

• $2 \leq N \leq 250000$
• $1 \leq M \leq N-1$
• $0 \leq A_i \leq N-1$
• 所有输入的值均为整数。

样例解释 1

可以如下进行操作，在 $2$ 次操作内达成目标。

• 初始状态：$A=(0,1,1)$
• 第 $1$ 次操作：选择 $A_1,A_2$，操作后 $A=(1,2,1)$。
• 第 $2$ 次操作：选择 $A_2,A_3$，操作后 $A=(1,0,2)$。

无法在少于 $2$ 次操作内达成目标，因此答案为 $2$。

由 ChatGPT 4.1 翻译