Задача C. Упаковка конфет

Автор:О. Туфанов, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:50  

Условие

Кондитерская фабрика изготовила партию конфет N различных сортов. В партию входит ai конфет i-го сорта.

Конфеты упаковываются в коробки двух видов: обычные и ассорти. В каждой из обычных коробок после упаковки должно оказаться ровно M конфет какого-нибудь одного сорта, а в каждой коробке ассорти — ровно N конфет, по одной каждого сорта.

Требуется определить максимально возможное значение M. Например, если изготовлено 15, 19 и 55 конфет трёх разных сортов, то их следует упаковывать в обычные коробки по 4 штуки, после чего останутся конфеты для 3 коробок ассорти.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел ai.

Формат выходного файла

В выходном файле должно содержаться единственное число — максимальное значение M.

Ограничения

2 ≤ N ≤ 105; 1 ≤ ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 
4 9
5
2
3
7 7 7
7

0.114s 0.019s 15