CF1649B.Game of Ball Passing

Daniel is watching a football team playing a game during their training session. They want to improve their passing skills during that session.

The game involves $n$ players, making multiple passes towards each other. Unfortunately, since the balls were moving too fast, after the session Daniel is unable to know how many balls were involved during the game. The only thing he knows is the number of passes delivered by each player during all the session.

Find the minimum possible amount of balls that were involved in the game.

丹尼尔正在观看一支足球队在训练课中的比赛。他们希望借此提升传球技巧。

该比赛涉及 $n$ 名球员，彼此之间进行了多次传球。不幸的是，由于球速过快，训练结束后丹尼尔无法确定比赛中总共使用了多少个球。他唯一知道的是：每名球员在整个训练过程中完成的传球次数。

请找出比赛中可能涉及的最少球数。

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^5$) — the number of players.

The second line of the test case contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$), where $a_i$ is the number of passes delivered by the $i$-th player.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.

输入数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示玩家数量。

每个测试用例的第二行包含一个整数序列 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 位玩家完成的传球次数。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case print a single integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the first test case, with the only ball, the game can go like this:

$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$.

In the second test case, there is no possible way to play the game with only one ball. One possible way to play with two balls:

$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$.

$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$

In the third example, there were no passes, so $0$ balls are possible.

在第一个测试用例中，仅有一个球时，游戏可能按如下方式进行：

$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$。

在第二个测试用例中，仅使用一个球无法进行游戏。使用两个球的一种可能方式进行如下：

$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$。

$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$

在第三个示例中，没有发生任何传球，因此可以使用 $0$ 个球。