← 返回题目列表

Codeforces · 2074/B

B. 第三面

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

粉红士兵给了你一个由 $$$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$$$。

输出

对于每个测试用例,在单独的行上输出唯一最后一个元素的最大可能值。

示例

输入
复制

4
1
10
3
998 244 353
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3

输出
复制

10
1593
11
39

注意

在第一个测试用例中,已经只有一个元素。最后一个元素的值为 $$$10$$$。

在第二个测试用例中,$$$a$$$ 最初是 $$$[998,244,353]$$$。以下一系列操作是有效的:

  1. 删除 $$$a_2=244$$$ 和 $$$a_3=353$$$,并将 $$$596$$$ 附加到 $$$a$$$ 的末尾。 $$$a$$$ 现在是 $$$[998,596]$$$。
  2. 删除 $$$a_1=998$$$ 和 $$$a_2=596$$$,并将 $$$1593$$$ 附加到 $$$a$$$ 的末尾。 $$$a$$$ 现在是 $$$[1593]$$$。

可以证明,唯一的最后一个元素不能大于$$$1593$$$。因此,答案是$$$1593$$$。