Ali is a top competitive programmer in his class (no one has a higher rating than him). He practices daily, even through exams.
Ali loves to help his friends and encourage them to practice. But he has one problem though, when it comes to competitors (people with the same rating as him), he gets obsessed with what they're doing and can’t focus on anything else but keeping an eye on them at all times.
And apparently, all of Ali's competitors (those who share the same highest rating) have the same issue as Ali, they can't focus when someone of their rating is around (is it a spreading disease??).
Ali’s coach doesn’t have time to fix the issue at hand, but what he can do instead is to distribute the students into 2 groups in such a way that Ali and his competitors are not distracted and be available to help all the other students (Ali and his competitors can watch students’ progress only if they belong to the same group).
Ali's coach loves him, so he will put the maximum number of students in his group.
Help Ali’s coach to distribute the students into at most 2 groups as needed, such that each group has at least one top competitive programmer and all top competitive programmers don't have any competitors in the same group.
The input consists of multiple test cases. The first line contains a single integer $t $ $(1 \le t \le 10^4)$ the number of test cases.
The first line of each test case contains an integer $n$ $(1 \le n \le 2 \cdot 10^5)$ -- the number of students.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n$ $(1 \le a_i \le 10^9)$ -- the ratings of the students.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
If it's possible to distribute the students into at most 2 groups with the mentioned constraints, print the maximum number of students in Ali's group, otherwise print -1.
In the first test case, we know that Ali's level is 8 and there is one other competitor so the groups will look like: {1,8} , {8}
In the second test case, there is no need to distribute the students into 2 groups, as Ali has no competitors.
| Input | Output |
|---|---|
2 3 1 8 8 6 1 2 3 4 5 6 Copy
|
2 6 Copy
|
We will look for the number of Ali’s competitors; which is the number of occurrences of the maximum rating - 1 (Ali’s rating ).
Since Ali has the highest rating, any competitor might have a rating exactly like Ali’s.
If the number of competitors is 0, there is no need to distribute the students.
If the number of competitors is 1, we will put this competitor in one group and the rest of the students in Ali’s group.
If the number of competitors is more than 1, we cant distribute the students into 2 groups and satisfy the problem’s conditions.