← 返回题目列表

Codeforces · 1649/B

B. 传球游戏

中文机器翻译题面 查看原题

丹尼尔正在观看一支足球队在训练期间进行的比赛。他们希望在那次训练中提高他们的传球技巧。

游戏涉及 $$$n$$$ 名玩家,相互进行多次传球。不幸的是,由于球移动得太快,比赛结束后丹尼尔无法知道比赛中涉及了多少个球。他唯一知道的是每个球员在整个训练过程中传球的次数。

求游戏中涉及的最小可能球数。

输入

输入数据中有多个测试用例。第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

4
4
2 3 3 2
3
1 5 2
2
0 0
4
1000000000 1000000000 1000000000 1000000000

输出 #1

1
2
0
1

注意

在第一个测试用例中,只有一个球,游戏可以这样进行:

$$$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 \右箭头 3 \右箭头 2 \右箭头 1$$$

在第三个示例中,没有传球,因此 $$$0$$$ 球是可能的。