time limit per test
2 seconds
memory limit per test
256 megabytes
The pink soldiers have given you a sequence aa consisting of nn positive integers.
You must repeatedly perform the following operation until there is only 11 element left.
- Choose two distinct indices ii and jj.
- Then, choose a positive integer value xx such that there exists a non-degenerate triangle∗∗ with side lengths aiai, ajaj, and xx.
- Finally, remove two elements aiai and ajaj, and append xx to the end of aa.
Please find the maximum possible value of the only last element in the sequence aa.
∗∗A triangle with side lengths aa, bb, cc is non-degenerate when a+b>ca+b>c, a+c>ba+c>b, b+c>ab+c>a.
Input
Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104). The description of the test cases follows.
The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105).
The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000) — the elements of the sequence aa.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case, output the maximum possible value of the only last element on a separate line.
Example
Input
Copy
4
1
10
3
998 244 353
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3
Output
Copy
10 1593 11 39
Note
On the first test case, there is already only one element. The value of the only last element is 1010.
On the second test case, aa is initially [998,244,353][998,244,353]. The following series of operations is valid:
- Erase a2=244a2=244 and a3=353a3=353, and append 596596 to the end of aa. aa is now [998,596][998,596].
- Erase a1=998a1=998 and a2=596a2=596, and append 15931593 to the end of aa. aa is now [1593][1593].
It can be shown that the only last element cannot be greater than 15931593. Therefore, the answer is 15931593.
解题说明：此题是一道数学题，采用贪心算法，找规律能发现为了保证添加的数尽可能大，则为每次从数列中取的两个数之和减去1。这样计算下来就是减去n-1个1（因为去掉两个数又增加了一个数，等于每次只少了一个数，最后还保留一个数）。所以直接求和即可。
#include <stdio.h>
int main()
{int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);int a[n], sum = 0;for (int i = 0; i < n; i++) {scanf("%d ", &a[i]);sum += a[i];}printf("%d\n", sum - n + 1);}return 0;
}