题目描述

给定一个长度为 $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$。如果可以，输出所需的最小操作次数。

样例 1

输入

3 2
0 1 1

输出

2

样例 2

输入

5 2
0 4 2 3 1

输出

0

样例 3

输入

4 2
0 0 1 2

输出

-1

样例 4

输入

20 15
5 14 18 0 8 5 0 10 6 5 11 2 10 10 17 9 8 14 4 4

输出

10

说明/提示

限制条件

• $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 翻译