CF1649B Game of Ball Passing

Daniel 正在观看一个足球队在训练期间进行的一场比赛。他们希望在这次训练中提升自己的传球技巧。 比赛中有 $n$ 名球员，他们之间进行了多次传球。不幸的是，由于球速太快，训练结束后 Daniel 无法知道比赛中到底用了多少个球。他唯一知道的是每个球员在整个训练期间传球的次数。 请你求出比赛中可能使用的最少球数。

输入包含若干组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示球员的数量。 每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 位球员传球的次数。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示本题的答案。

在第一个测试用例中，只用一个球，比赛可以这样进行： $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$ 个球。 由 ChatGPT 4.1 翻译