Вас попросили присмотреть за вашим племянником, который любит играть с кубиками необычным способом.
У него есть \(n\) коробок и в \(i\)-й коробке лежит \(a_i\) кубиков. Его игра состоит из двух ходов:
- он выбирает произвольную коробку \(i\);
- он пытается переложить все кубики из \(i\)-й коробки в другие коробки.
Если у него получится сделать равное количество кубиков в каждой из оставшихся
\(n - 1\) коробок, то он обрадуется, а если не получится — расстроится. Заметьте, что ваш племянник может перекладывать кубики только из выбранной коробки; он не может перекладывать кубики из других коробок.
Вы не хотите, чтобы ваш племянник расстраивался, поэтому вы решили доложить несколько дополнительных кубиков в некоторые коробки так, что независимо от того, какую коробку \(i\) он выберет, он не расстроится. Какое минимальное количество кубиков вам нужно доложить?
Выходные данные
Для каждого набора входных данных, выведите одно целое число — минимальное количество кубиков, которое вам нужно доложить. Можно доказать, что ответ всегда существует, то есть количество кубиков конечное.
Примечание
В первом наборе входных данных, вы можете, например, положить один дополнительный блок в первую коробку и сделать \(a = [4, 2, 2]\). Если ваш племянник выберет коробку с \(4\) кубиками, то он переложит два кубика во вторую коробку и два кубика в третью. Если же он выберет коробку с \(2\) кубиками, то оно переложит эти два кубика в другую коробку с \(2\) кубиками.
Во втором наборе, вам не нужно докладывать кубики, потому что независимо от того, какую коробку он выберет, он всегда сможет выровнять количество кубиков в других коробках.
В третьем наборе, вам нужно доложить хотя бы \(3\) кубика. Например, вы можете положить \(2\) кубика в первую коробку и \(1\) кубик в третью. Вы получите \(a = [2, 3, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
3 2 2
4
2 2 3 2
3
0 3 0
|
1
0
3
|