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

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

  1. Выберите любой набор из $$$k$$$ различных индексов $$$S = \{i_1, i_2, \ldots, i_k\}$$$, где $$$1 \le i_j \le n$$$ для всех $$$1\le j\le k$$$.
  2. Вычислите сумму $$$x = a_{i_1} + a_{i_2} + \cdots + a_{i_k}$$$, и присвойте $$$y = x - \left\lfloor \frac{x}{k} \right\rfloor \cdot k$$$.
  3. Среди выбранных элементов $$$a_{i_1}, \ldots, a_{i_k}$$$ уменьшите $$$y$$$ наименьших элементов на $$$1$$$.
    • Если два элемента имеют разные значения ($$$a_i\ne a_j$$$), то меньшим является тот, который имеет меньшее значение.
    • Если два элемента имеют одинаковое значение ($$$a_i= a_j$$$), меньшим считается элемент с меньшим индексом.
    • Если $$$y=0$$$, ни один элемент не уменьшается.

Ваша задача — определить минимально возможное значение суммы элементов массива $$$a$$$, которое можно достичь после выполнения операции любое количество раз, или сообщить, что её можно уменьшать бесконечно.

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

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

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

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Если сумма элементов массива $$$a$$$ может быть уменьшена бесконечно, выведите $$$-1$$$.

Пример
Входные данные
3
2
2 1
4
3 3 3 3
8
1 2 3 4 5 6 7 8
Выходные данные
2
12
-1
Примечание

В первом наборе входных данных мы можем выполнить только одну операцию один раз над всем массивом, что приводит к массиву $$$a = [2, 0]$$$, после чего никакая операция не приводит к уменьшению.

Во втором наборе входных данных никакая операция не приводит к уменьшению, и, следовательно, ответ — сумма элементов массива.

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