← 返回题目列表

Codeforces · 1826/A

A. 相信没有人

中文机器翻译题面 查看原题

有一群 $$$n$$$ 人。他们中的一些人可能是骗子,总是说谎。别人总是说实话。第 $$$i$$$ 人说“我们中间至少有 $$$l_i$$$ 骗子”。确定人们所说的是否矛盾,或者是否可能。如果可能,输出该组中说谎者的数量。如果有多个可能的答案,则输出其中任意一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$l_i$$$ ($$$0 \leq l_i \leq n$$$) — 第 $$$i$$$ 人所说的数字。

保证所有$$$n$$$的总和不超过$$$10^4$$$。

输出

对于每个测试用例输出一个整数。如果人们所说的相互矛盾,则输出$$$-1$$$。否则,输出该组中说谎者的数量。如果有多个可能的答案,则输出其中任意一个。

示例

输入 #1

7
2
1 2
2
2 2
2
0 0
1
1
1
0
5
5 5 3 3 5
6
5 3 6 6 3 5

输出 #1

1
-1
0
-1
0
3
4

注意

在第一个示例中,唯一可能的答案是第二个人是骗子,因此答案是 $$$1$$$ 骗子。

在第二个例子中,可以证明我们不能选择说谎者,从而满足所有要求。

在第三个例子中,每个人都说实话,所以答案是$$$0$$$ 骗子。