CF2074B The Third Side

粉色士兵们给了你一个由 $n$ 个正整数组成的序列 $a$。 你必须重复执行以下操作直到序列中只剩下 $1$ 个元素： - 选择两个不同的下标 $i$ 和 $j$ - 选择一个正整数 $x$，使得存在一个非退化三角形$^{\text{∗}}$，其边长为 $a_i$、$a_j$ 和 $x$ - 删除这两个元素 $a_i$ 和 $a_j$，并将 $x$ 追加到序列 $a$ 的末尾 请找出最终序列中唯一剩余元素可能的最大值。 $^{\text{∗}}$当边长为 $a$、$b$、$c$ 的三角形满足 $a + b > c$、$a + c > b$ 且 $b + c > a$ 时，该三角形是非退化的。

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

对于每个测试用例，在单独一行中输出最终剩余元素的可能最大值。

在第一个测试用例中，序列已经只有一个元素。最终剩余元素的值为 $10$。 在第二个测试用例中，初始序列为 $[998, 244, 353]$。以下操作序列是合法的： 1. 删除 $a_2 = 244$ 和 $a_3 = 353$，并追加 $596$ 到序列末尾。此时 $a$ 变为 $[998, 596]$ 2. 删除 $a_1 = 998$ 和 $a_2 = 596$，并追加 $1593$ 到序列末尾。此时 $a$ 变为 $[1593]$ 可以证明最终元素不可能超过 $1593$。因此答案为 $1593$。 翻译由 DeepSeek R1 完成