Задачі
Папа Карло
Папа Карло
Папа Карло робив Буратіно усе своє життя. Він робив десятки, сотні чи навіть, може бути, тисячі гарненьких і охайно одягнених хлопчиків з довгими носами. У папи Карло у сараї була куча дерев'яних палочок, які він тримав для майбутніх носів. У минулу п'ятницю папа Карло отримав термінове замовлення на виробництво партії Буратіно з однаковими носами. Він вирішив використати усі свої дерев'янні палочки для виготовлення носів.
Для цього папа Карло виміряв усі палочки і виявив, що їх довжини є натуральними числами. Потім майстер став вибирати довільні дві палочки різної довжини і відпилювати від більш довгої кусок, який співпадав по довжині з короткою. В результаті він отримував три палочки, які повертались назад у загальну купу. Папа Карло діяв за такою схемою, доки усі палочки у купці не ставали однакової довжини.
Допоможіть папі Карло і порахуйте кількість носів!
Напишіть програму, яка за кількістю палочок \textbf{n} та їх довжинам \textbf{l_i} (\textbf{i} = \textbf{1}, ..., \textbf{n}) буде визначати кількість отриманих носів.
\textit{\textbf{Приклад}}. Нехай у папи Карло є дві палочки з довжинами \textbf{4} см та \textbf{6} см. Після першого відпилювання буде три палочки: одна довжиною \textbf{2} см і дві по \textbf{4} см. Після другого відпилювання стане чотире полочки з довжинами \textbf{2}, \textbf{2}, \textbf{2} і \textbf{4} см. І, нарешті, ми отримаємо п'ять носів довжиною \textbf{2} сантиметри.
\InputFile
Перший рядок містить ціле число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10000}) -- кількість палочок-носів. Наступні \textbf{n} рядків містять довжини \textbf{n} палочок, по одному у рядку (\textbf{1} ≤ \textbf{l}_i ≤\textbf{10000}; \textbf{1} ≤ \textbf{i} ≤ \textbf{n}).
\OutputFile
У вихідний файл необхідно вивести єдине число \textbf{k} -- число палочок у купці по завершенню роботи папи Карло.
Вхідні дані #1
3 2 7 5
Вихідні дані #1
14
Вхідні дані #2
2 6 4
Вихідні дані #2
5