D-mex_牛客小白月赛113

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给你一个由 $n$ 个自然数（非负整数）组成的数组 $\{a_1,a_2,\dots,a_n\}$ ，我们定义一轮操作：
$\hspace{23pt}\bullet\,$ 计算出当前数组的 $\operatorname{mex}$ ，随后，使得所有的 $a_i := \max\{0,a_i - \operatorname{mex}\}$ 。换句话说，对于任意的 $1\leqq i\leqq n$ ，使得 $a_i\gets \max \{0,a_i - \operatorname{mex}\}$ 。
$\hspace{15pt}$ 小牛想知道你至少需要执行多少轮（也可以不执行）操作，才能使得数组 $a$ 中的每个数都相同？如果无法使得数组 $a$ 中的每个数都相同，则直接输出 $-1$ 。

$\hspace{15pt}$ 整数数组的 $\operatorname{mex}$ 定义为没有出现在数组中的最小非负整数。例如 $\operatorname{mex} \{1,2,3 \} =0$ 、 $\operatorname{mex} \{0,2,5\} =1$ 。

输入描述:

第一行输入一个整数  代表数组中的元素数量。 
第二行输入  个整数  代表数组中的元素。

输出描述:

如果无法使得数组  中的每个数都相同，则直接输出 ；否则，输出一个整数，代表至少需要执行的轮数。

示例1

输入

复制

6
0 1 2 3 4 5

输出

复制

说明

在这个样例中，第一轮数组的  为 ，所以：
对于第一个元素 ，使用  替换；
对于第二个元素 ，使用  替换；
对于第三个元素 ，使用  替换；
对于第四个元素 ，使用  替换；
对于第五个元素 ，使用  替换；
对于第六个元素 ，使用  替换。
得到数组 ，满足题干条件。所以，至少需要执行  轮操作。

示例2

输入

复制

5
3 1 2 4 5

输出

复制

-1

说明

在这个样例中，由于第一轮数组的  为 ，所以无论执行多少次操作，数组都不会改变，所以无法使所有数变为相同值。

示例3

输入

复制

6
0 1 3 4 7 9

输出

复制

说明

在这个样例中：
第一轮操作：，操作完后数组变为 ； 
第二轮操作：，操作完后数组变为 ；
第三轮操作：，操作完后数组变为 ； 
第四轮操作：，操作完后数组变为 ； 
第五轮操作：，操作完后数组变为 。
综上所述，至少需要执行  轮操作。