В Шервуде мы судим человека не по его богатству, а по его заслугам.
Оглянитесь вокруг, богатые становятся богаче, а бедные — беднее. Нам нужно отнять у богатых и отдать бедным. Нам нужен Робин Гуд!
В городе живут \(n\) человек. Сейчас богатство \(i\)-го человека составляет \(a_i\) золота. Но угадайте что? Самый богатый человек только что нашел дополнительную бочку золота!
Более формально, найдите \(a_j=max(a_1, a_2, \dots, a_n)\), измените \(a_j\) на \(a_j+x\), где \(x\) — это количество золота в бочке. Если есть несколько максимумов, можно взять любой из них.
Человек несчастен, если его богатство строго ниже половины среднего богатства\(^{\text{∗}}\). Если строго больше половины общего населения \(n\) несчастны, Робин Гуд появится по народному требованию.
Определите минимальное значение \(x\), необходимое для появления Робина Гуда, или выведите \(-1\), если это невозможно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество золота, которое самый богатый человек должен найти, чтобы Робин Гуд пришел в город. Если это невозможно, выведите \(-1\) вместо этого.
Примечание
В первом наборе входных данных невозможно, чтобы один человек был несчастным.
Во втором наборе входных данных всегда есть \(1\) счастливый человек (самый богатый).
В третьем наборе входных данных дополнительное золото не требуется, поэтому ответ \(0\).
В четвертом наборе входных данных, после добавления \(15\) золота, среднее богатство становится \(\frac{25}{4}\), и половина этого среднего составляет \(\frac{25}{8}\), в результате чего \(3\) человека оказываются несчастными.
В пятом наборе входных данных, после добавления \(16\) золота, среднее богатство становится \(\frac{31}{5}\), в результате чего \(3\) человека оказываются несчастными.
Примеры
| № | Входные данные | Выходные данные |
|
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
|