粉红士兵给了你一个由 $$$n$$$ 正整数组成的序列 $$$a$$$。
您必须重复执行以下操作 直到只剩下 $$$1$$$ 元素.
- 选择两个 不同 上面写着 索引 $$$i$$$ 和 $$$j$$$。
- 然后,选择一个正整数值$$$x$$$,使得存在 非退化三角形$$$^{\text{*}}$$$,边长为 $$$a_i$$$、$$$a_j$$$ 和 $$$x$$$。
- 最后,删除两个元素 $$$a_i$$$ 和 $$$a_j$$$,并将 $$$x$$$ 附加到 $$$a$$$ 的末尾。
请找出序列 $$$a$$$ 中唯一最后一个元素的最大可能值。
$$$^{\text{*}}$$$当 $$$a+b \gt c$$$、$$$a+c \gt b$$$、$$$b+c \gt a$$$ 时,边长为 $$$a$$$、$$$b$$$、$$$c$$$ 的三角形是非退化的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 1000$$$) — 序列 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出唯一最后一个元素的最大可能值。
示例
输入复制
41103998 244 35351 2 3 4 599 9 8 2 4 4 3 5 3
输出复制
10 1593 11 39
注意
在第一个测试用例中,已经只有一个元素。最后一个元素的值为 $$$10$$$。
在第二个测试用例中,$$$a$$$ 最初是 $$$[998,244,353]$$$。以下一系列操作是有效的:
- 删除 $$$a_2=244$$$ 和 $$$a_3=353$$$,并将 $$$596$$$ 附加到 $$$a$$$ 的末尾。 $$$a$$$ 现在是 $$$[998,596]$$$。
- 删除 $$$a_1=998$$$ 和 $$$a_2=596$$$,并将 $$$1593$$$ 附加到 $$$a$$$ 的末尾。 $$$a$$$ 现在是 $$$[1593]$$$。
可以证明,唯一的最后一个元素不能大于$$$1593$$$。因此,答案是$$$1593$$$。