Задача D. Разноцветные кубики ≡

Условие

На завод, занимающийся производством игрушек, привезли исходные материалы в виде набора наклеек с разного рода цветными изображениями. Указанные наклейки было решено задействовать при заготовке детских кубиков (по одной на каждую грань). При этом, по задумке дизайнеров, каждый такой кубик не должен содержать наклеек с одинаковыми изображениями. Кубики, состоящие из одного и того же набора наклеек, объединяются в отдельные группы. В свою очередь, наклейки одного вида не могут встречаться на кубиках, принадлежащих к разным группам.

Требуется определить максимально возможное число таких кубиков, которые можно покрыть имеющимся набором наклеек.

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

В заголовке входного файла "input.txt" хранится число доступных разновидностей наклеек n. Далее следует набор из n значений A_i, указывающих число наклеек каждого вида.

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

Выходной файл "output.txt" должен содержать максимально возможное число кубиков.

Ограничения

0 < n ≤ 10⁶, 0 < A_i ≤ 10⁹

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

8

23
31
742
4
5
84
6
19

6

5

12
145
7
94
2

0