310387: CF1826A. Trust Nobody

A. Trust Nobodytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is a group of $n$ people. Some of them might be liars, who always tell lies. Other people always tell the truth. The $i$-th person says "There are at least $l_i$ liars amongst us". Determine if what people are saying is contradictory, or if it is possible. If it is possible, output the number of liars in the group. If there are multiple possible answers, output any one of them.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$).

The second line of each test case contains $n$ integers $l_i$ ($0 \leq l_i \leq n$) — the number said by the $i$-th person.

It's guaranteed that the sum of all $n$ does not exceed $10^4$.

Output

For each test case output a single integer. If what people are saying is contradictory, output $-1$. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.

ExampleInput

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

Output

1
-1
0
-1
0
3
4

Note

In the first example, the only possible answer is that the second person is a liar, so the answer is $1$ liar.

In the second example, it can be proven that we can't choose the liars so that all the requirements are satisfied.

In the third example, everybody tells the truth, so the answer is $0$ liars.

题目大意：
这是一个关于判断一群人中哪些是总是说谎的人的问题。这群人中的每个人都会说：“我们当中至少有$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$。否则，输出这群中说谎者的数量。如果有多个可能的答案，输出其中任何一个。

示例：
输入：
```
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
0
-1
0
3
4
```
注意：
- 在第一个示例中，唯一可能的答案是第二个人是说谎者，所以答案是1个说谎者。
- 在第二个示例中，可以证明我们无法选择说谎者以使所有要求都得到满足。
- 在第三个示例中，每个人都说实话，所以答案是0个说谎者。题目大意： 这是一个关于判断一群人中哪些是总是说谎的人的问题。这群人中的每个人都会说：“我们当中至少有$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$。否则，输出这群中说谎者的数量。如果有多个可能的答案，输出其中任何一个。 示例： 输入： ``` 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 0 -1 0 3 4 ``` 注意： - 在第一个示例中，唯一可能的答案是第二个人是说谎者，所以答案是1个说谎者。 - 在第二个示例中，可以证明我们无法选择说谎者以使所有要求都得到满足。 - 在第三个示例中，每个人都说实话，所以答案是0个说谎者。