|Codeforces Round #693 (Div. 3)|
During their New Year holidays, Alice and Bob play the following game using an array $$$a$$$ of $$$n$$$ integers:
If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.
For example, if $$$n = 4$$$ and $$$a = [5, 2, 7, 3]$$$, then the game could go as follows (there are other options):
You want to find out who will win if both players play optimally. Note that there may be duplicate numbers in the array.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$.
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$ used to play the game.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output on a separate line:
4 4 5 2 7 3 3 3 2 1 4 2 2 2 2 2 7 8
Bob Tie Alice Alice