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

Вам дан массив целых чисел $$$[a_1, a_2, \ldots, a_n]$$$. Изначально все элементы разблокированы.

Вы можете выполнить следующую операцию над массивом $$$a$$$ любое количество раз (возможно, ноль):

  1. Выберите целое число $$$k$$$ ($$$1 \le k \le n$$$) и ровно $$$k$$$ различных индексов. Элементы с этими индексами блокируются на время текущей операции. Стоимость этого шага равна $$$k$$$.

  2. Выберите одно из следующих двух действий:

    • Увеличить каждый разблокированный элемент на $$$1$$$;
    • Уменьшить каждый разблокированный элемент на $$$1$$$.
    Этот шаг не требует дополнительных затрат.

  3. Разблокируйте все элементы. Этот шаг не требует дополнительных затрат.

Общая стоимость равна сумме стоимостей всех выполненных операций.

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

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

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

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

Пример
Входные данные
5
3
1 2 3
2
-1 -1
4
18 -2 9 11
9
9 9 8 2 4 4 3 5 3
3
6 67 7
Выходные данные
2 2
0 0
22 20
19 7
61 61
Примечание

В первом наборе входных данных оптимальна следующая последовательность операций:

  1. Заблокируем первый элемент и уменьшим все разблокированные элементы на $$$1$$$. Массив изменится с $$$[1,2,3]$$$ на $$$[1,1,2]$$$. Стоимость этой операции равна $$$1$$$.

  2. Заблокируем третий элемент и увеличим все разблокированные элементы на $$$1$$$. Массив изменится с $$$[1,1,2]$$$ на $$$[2,2,2]$$$. Стоимость этой операции равна $$$1$$$.

Общая стоимость равна $$$1+1=2$$$, при этом выполнено ровно $$$2$$$ операции. Невозможно сделать все элементы равными с меньшей общей стоимостью.

Во втором наборе входных данных все элементы уже равны, поэтому минимальная общая стоимость и минимальное количество операций равны $$$0$$$.