← 返回题目列表

Codeforces · 1767/B

B. 座塔

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

有 $$$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]$$$。