Papa Carlo#2549
Papa Carlo was making Buratino all his life. He made dozens, hundreds, or maybe thousands of beautiful and well-dressed boys with long noses. Papa Carlo had a bunch of wooden sticks in his barn. He kept them for future noses. Last Friday, Papa Carlo received an urgent order to produce a batch of Buratino with the same noses. He decided to use all his wooden sticks for the noses.
For this, Papa Carlo measured all sticks and found that their lengths are natural numbers. Then, the Master began to choose any two sticks of different lengths and saw off the longer one by the length of the shorter one. As a result, three sticks were produced. All of these sticks were sent back to the pile. So Papa Carlo had been working until all the sticks in the pile became the same length.
Help Papa Carlo and count the number of noses!
Write a program that, using the number of sticks and their lengths l_i (i = 1, \ldots, n), will determine the resulting number of noses.
Example. Let Papa Carlo have two sticks with the lengths of cm and cm. After the first sawing, there will be three sticks: one cm stick and two cm sticks. After the second sawing, there will be four sticks with the lengths of , , , and cm. Finally, we will get five pieces of equal length cm.
The first line contains an integer (1 \leq n \leq 10000) — the number of nose sticks. In the following lines, integers are given, which are the lengths of the sticks, one number per line (1 \leq l_i \leq 10000, 1 \leq i \leq n).
The output file should contain a single integer — the number of sticks in the pile at the end of Papa Carlo's work.
Example 1
Example 2