Minimum Votes to Win

In an election, each candidate has received a certain number of votes. Your task is to compute the minimum number of additional votes required for the candidate with the least votes to win the election by having strictly more votes than any other candidate.

More formally, if the vote counts for a test case are given as \(a_1, a_2, \dots, a_n\), let \(M = \max\{a_1, a_2, \dots, a_n\}\) and \(m = \min\{a_1, a_2, \dots, a_n\}\). The additional votes needed is:

\(\text{Answer} = M + 1 - m\)

For example, if the votes are [10, 20, 15], then \(M = 20\) and \(m = 10\), so the candidate with the fewest votes needs \(20 + 1 - 10 = 11\) extra votes to win.

inputFormat

The first line contains an integer (T) representing the number of test cases. For each test case:\n - The first line contains an integer (N), the number of candidates.\n - The second line contains (N) space-separated integers, where each integer represents the vote count of a candidate.

outputFormat

For each test case, output a single integer on a new line indicating the minimum additional votes required for the candidate with the least votes to secure a win (i.e. have strictly more votes than any other candidate).## sample

2
3
10 20 15
4
5 5 5 5

11
1