Папа Карло всю свою жизнь
мастерил Буратино. Он изготовил десятки, сотни, а, может быть, и тысячи
красивых нарядных деревянных мальчишек с длинными носами. В сарае у папы Карло
была куча всяких деревянных заготовок. А отдельно – на чердаке он хранил
деревянные палочки – будущие носы.
В прошлую пятницу Папа Карло
получил срочный заказ изготовить партию Буратино с одинаковыми носами. Он решил
использовать все имеющиеся заготовки носов.
Для этого папа Карло перемерял
все заготовки, и оказалось, что их длины есть натуральные числа. Дальше мастер
стал выбирать из кучи две произвольные заготовки разной длины и отпиливать от
большей из них кусок равный длине меньшей. В итоге из двух заготовок получалось
три. Все эти заготовки отправлялись обратно в кучу. Так папа Карло действовал
до тех пор, пока все заготовки в куче не стали одной длины.
Помогите папе Карло и посчитайте
количество получившихся носов!
Напишите программу, которая по
заданным количеству исходных заготовок n и их длинам li (i=1,…,n) определяет количество получившихся заготовок после
того, как папа Карло завершит свою работу.
Пример. Пусть у папы Карло
было 2 заготовки с длинами 4 см и 6 см. После первого опиливания получатся три
заготовки с длинами: одна заготовка длиною 2 см и две заготовки по 4 см. После второго опиливания имеем уже четыре заготовки с длинами 2, 2, 2, 4 см. И, наконец, после третьего опиливания получаем окончательно 5 заготовок одинаковой длины по 2 см.
Ограничения
1 <= n <= 10000; 1<= li <= 10000;
1 <= i <= n.
Входные данные
Первая строка входного файла
содержит целое число n (количество заготовок
носов). В последующих n строках
заданы n целых чисел (длины заготовок) по
одному числу на строке.
Выходные данные
В выходной файл должно быть
записано одно целое число k – количество
заготовок в куче к моменту окончания работы папы Карло.
Примеры
