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