시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 29 | 15 | 13 | 48.148% |
Professor Zhang has $n$ kinds of characters, and the quantity of the $i$-th character is $a_i$. Professor Zhang wants to use all the characters to build several palindromic strings. He also wants to maximize the length of the shortest palindromic string.
For example, let there be $4$ kinds of characters denoted as 'a
', 'b
', 'c
', 'd
', and let their quantities be $\{2, 3, 2, 2\}$, respectively. Professor Zhang can build ("acdbbbdca
"), or ("abbba
" and "cddc
"), or ("aca
", "bbb
" and "dcd
"), or ("acdbdca
and "bb
"). The first is the optimal solution where the length of the shortest palindromic string is $9$.
Note that a string is called palindromic if it can be read the same way in either direction.
There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^5$): the number of kinds of characters. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^4$).
There are at most $110$ test cases, and the total size of the input is at most $6$ mebibytes.
For each test case, output an integer denoting the answer.
4 4 1 1 2 4 3 2 2 2 5 1 1 1 1 1 5 1 1 2 2 3
3 6 1 3