CF2074B The Third Side

The pink soldiers have given you a sequence $ a $ consisting of $ n $ positive integers. You must repeatedly perform the following operation until there is only $ 1 $ element left. - Choose two distinct indices $ i $ and $ j $ . - Then, choose a positive integer value $ x $ such that there exists a non-degenerate triangle $ ^{\text{∗}} $ with side lengths $ a_i $ , $ a_j $ , and $ x $ . - Finally, remove two elements $ a_i $ and $ a_j $ , and append $ x $ to the end of $ a $ . Please find the maximum possible value of the only last element in the sequence $ a $ . $ ^{\text{∗}} $ A triangle with side lengths $ a $ , $ b $ , $ c $ is non-degenerate when $ a+b > c $ , $ a+c > b $ , $ b+c > a $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 1000 $ ) — the elements of the sequence $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the maximum possible value of the only last element on a separate line.

On the first test case, there is already only one element. The value of the only last element is $ 10 $ . On the second test case, $ a $ is initially $ [998,244,353] $ . The following series of operations is valid: 1. Erase $ a_2=244 $ and $ a_3=353 $ , and append $ 596 $ to the end of $ a $ . $ a $ is now $ [998,596] $ . 2. Erase $ a_1=998 $ and $ a_2=596 $ , and append $ 1593 $ to the end of $ a $ . $ a $ is now $ [1593] $ . It can be shown that the only last element cannot be greater than $ 1593 $ . Therefore, the answer is $ 1593 $ .