Шоколадная Фабрика

Вилли Вонка владеет шоколадной фабрикой, которая производит множество разных сладостей. Иногда Вилли Вонка раздаёт сладости бесплатно. Перед фабрикой выстраивается длиннющий ряд детишек и каждому что-нибудь вручают.

Скоро наступит очередной из таких довольно редких случаев. На этот раз было решено раздавать конфеты. Фабрика производит N различных видов конфет. Вилли Вонка собирается отдать каждому из детей набор из N-1 штук различных конфет. Беда только в том, что количества конфет разных видов могут различаться, и становится трудно подсчитать, скольким детям достанется подарок при такой схеме в наилучшем случае. Вот это вам и придётся сделать.

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

Первая строка содержит число N (2 ≤ N≤10000) – количество различных видов конфет.

Каждая i-ая из следующих N строк содержит одно число – количество конфет i-ого типа. Количество конфет одного типа будет в диапазоне от 1 до 500000000, включительно.

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

Единственное число – максимальное количество комплектов из N-1 конфет, которое можно получить, если распределять конфеты оптимально.