Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

C. Робин Гуд в городе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
В Шервуде мы судим человека не по его богатству, а по его заслугам.

Оглянитесь вокруг, богатые становятся богаче, а бедные — беднее. Нам нужно отнять у богатых и отдать бедным. Нам нужен Робин Гуд!

В городе живут $$$n$$$ человек. Сейчас богатство $$$i$$$-го человека составляет $$$a_i$$$ золота. Но угадайте что? Самый богатый человек только что нашел дополнительную бочку золота!

Более формально, найдите $$$a_j=max(a_1, a_2, \dots, a_n)$$$, измените $$$a_j$$$ на $$$a_j+x$$$, где $$$x$$$ — это количество золота в бочке. Если есть несколько максимумов, можно взять любой из них.

Человек несчастен, если его богатство строго ниже половины среднего богатства$$$^{\text{∗}}$$$. Если строго больше половины общего населения $$$n$$$ несчастны, Робин Гуд появится по народному требованию.

Определите минимальное значение $$$x$$$, необходимое для появления Робина Гуда, или выведите $$$-1$$$, если это невозможно.

$$$^{\text{∗}}$$$Среднее богатство определяется как общее богатство, деленное на общее население $$$n$$$, то есть $$$\frac{\sum a_i}{n}$$$, результат является вещественным числом.

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

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

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

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

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

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

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

Пример
Входные данные
6
1
2
2
2 19
3
1 3 20
4
1 2 3 4
5
1 2 3 4 5
6
1 2 1 1 1 25
Выходные данные
-1
-1
0
15
16
0
Примечание

В первом наборе входных данных невозможно, чтобы один человек был несчастным.

Во втором наборе входных данных всегда есть $$$1$$$ счастливый человек (самый богатый).

В третьем наборе входных данных дополнительное золото не требуется, поэтому ответ $$$0$$$.

В четвертом наборе входных данных, после добавления $$$15$$$ золота, среднее богатство становится $$$\frac{25}{4}$$$, и половина этого среднего составляет $$$\frac{25}{8}$$$, в результате чего $$$3$$$ человека оказываются несчастными.

В пятом наборе входных данных, после добавления $$$16$$$ золота, среднее богатство становится $$$\frac{31}{5}$$$, в результате чего $$$3$$$ человека оказываются несчастными.