D. Игра на массиве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ положительных целых чисел. Алиса и Боб будут играть в игру с этим массивом. Они будут поочередно делать ходы, при этом Алиса ходит первой.

На каждом ходу игрок должен выбрать значение $$$x \gt 0$$$, содержащееся в $$$a$$$. После этого

  1. игрок получает $$$1$$$ очко за каждое значение $$$x$$$ в массиве,
  2. каждое значение $$$x$$$ в массиве уменьшается на $$$1$$$ и становится равным $$$x-1$$$.
Обратите внимание, что игрок может выбрать число $$$x$$$ только если оно присутствует в $$$a$$$ в данный момент, поэтому каждый допустимый ход приносит положительное количество очков. Например, если массив равен $$$[3,8,5,8]$$$ и Алиса выбирает $$$x=8$$$, массив станет $$$[3,7,5,7]$$$, и Алиса заработает $$$2$$$ очка.

Игра заканчивается, когда нельзя выбрать $$$x$$$; то есть, когда все элементы массива равны нулю.

Учитывая, что оба игрока хотят максимизировать свои очки и играют оптимально, вычислите количество очков, которое каждый игрок получит в конце.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^{5}$$$) — размер массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{9}$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$2\cdot 10^{5}$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа: количество очков, которые получат Алиса и Боб, если оба будут играть оптимально.

Пример
Входные данные
3
3
2 1 1
5
3 3 3 5 5
4
9 9 9 9
Выходные данные
3 1
10 9
20 16
Примечание

Ссылка на визуализатор

В первом наборе входных данных Алиса первым ходом выберет $$$x=1$$$. Массив становится $$$[2,0,0]$$$, и она зарабатывает $$$2$$$ очка. После этого Боб вынужден выбрать $$$x=2$$$. Массив становится $$$[1,0,0]$$$, и Боб зарабатывает $$$1$$$ очко. Наконец, Алиса вынуждена выбрать $$$x=1$$$ и заработать еще одно очко. После этого массив становится $$$[0,0,0]$$$, и игра заканчивается. В итоге Алиса заканчивает с $$$3$$$ очками, а Боб с $$$1$$$ очком.

В третьем наборе входных данных каждый игрок будет уменьшать все элементы и зарабатывать по $$$4$$$ очка за каждый ход. Алиса заработает $$$5 \cdot 4 = 20$$$ очков, в то время как Боб заработает только $$$4\cdot 4 = 16$$$ очков.