Вас попросили присмотреть за вашим племянником, который любит играть с кубиками необычным способом.
У него есть $$$n$$$ коробок и в $$$i$$$-й коробке лежит $$$a_i$$$ кубиков. Его игра состоит из двух ходов:
Вы не хотите, чтобы ваш племянник расстраивался, поэтому вы решили доложить несколько дополнительных кубиков в некоторые коробки так, что независимо от того, какую коробку $$$i$$$ он выберет, он не расстроится. Какое минимальное количество кубиков вам нужно доложить?
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество коробок.
Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество кубиков в каждой коробке.
Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$10^5$$$.
Для каждого набора входных данных, выведите одно целое число — минимальное количество кубиков, которое вам нужно доложить. Можно доказать, что ответ всегда существует, то есть количество кубиков конечное.
3 3 3 2 2 4 2 2 3 2 3 0 3 0
1 0 3
В первом наборе входных данных, вы можете, например, положить один дополнительный блок в первую коробку и сделать $$$a = [4, 2, 2]$$$. Если ваш племянник выберет коробку с $$$4$$$ кубиками, то он переложит два кубика во вторую коробку и два кубика в третью. Если же он выберет коробку с $$$2$$$ кубиками, то оно переложит эти два кубика в другую коробку с $$$2$$$ кубиками.
Во втором наборе, вам не нужно докладывать кубики, потому что независимо от того, какую коробку он выберет, он всегда сможет выровнять количество кубиков в других коробках.
В третьем наборе, вам нужно доложить хотя бы $$$3$$$ кубика. Например, вы можете положить $$$2$$$ кубика в первую коробку и $$$1$$$ кубик в третью. Вы получите $$$a = [2, 3, 1]$$$.
Название |
---|