有 $$$n$$$ 座塔,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 塔由 $$$a_i$$$ 块组成。
在一次移动中,您可以将一个方块从 $$$i$$$ 塔移动到 $$$j$$$ 塔,但前提是 $$$a_i > a_j$$$。该举动使 $$$a_j$$$ 增加 $$$1$$$,并减少 $$$a_i$$$ $$$1$$$。您可以执行任意数量的移动(可能为零)。
移动后塔上$$$1$$$最多可以拥有多少块?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 塔的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 每个塔上的块数。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在进行任意次数的移动(可能为零)后,打印塔上可以拥有的最大块数 $$$1$$$。
示例
输入 #1
4 3 1 2 3 3 1 2 2 2 1 1000000000 10 3 8 6 7 4 1 2 4 10 1
输出 #1
3 2 500000001 9
注意
在第一个测试用例中,您可以将一个块从塔 $$$2$$$ 移动到塔 $$$1$$$,使块计数 $$$[2, 1, 3]$$$。然后将一个方块从 $$$3$$$ 塔移动到 $$$1$$$ 塔,使该方块计数为 $$$[3, 1, 2]$$$。塔 $$$1$$$ 中有 $$$3$$$ 块,并且你无法获得更大的数量。
在第二个测试用例中,您可以将块从任何塔 $$$2$$$ 或 $$$3$$$ 移动到塔 $$$1$$$,以便其中包含 $$$2$$$ 块。
在第三个测试用例中,您可以 $$$500000000$$$ 次将一个方块从塔 $$$2$$$ 移动到塔 $$$1$$$。之后块计数将为$$$[500000001, 500000000]$$$。