鸭子盈余

英文题名：C. Duck Surplus
来源：Codeforces 2237C
比赛：Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
时间限制：2 seconds
空间限制：256 megabytes

题目描述

给定若干堆鸭子的数量。你可以按题目规则移动鸭子，目标是使最终最大堆尽可能小。求这个最小可能值。

输入格式

第一行输入 $t$。每组输入 $n$ 和数组 $a$。所有 $n$ 之和不超过 $2\cdot10^5$。

输出格式

每组输出最小可能的最大堆大小。

样例

10
4
1 2 2 5
2
7 3
3
3 2 1
5
2 2 1 3 3
4
3 1 4 2
5
1 4 3 2 5
6
6 2 5 1 4 3
7
2 7 1 6 3 5 4
8
8 1 7 2 6 3 5 4
5
1000000000 999999999 999999998 999999997 999999996

5
10
6
3
6
14
21
26
36
4999999990