Maximum Identical Gift Boxes

You are given n types of items. The i-th type has a given quantity. Your task is to determine the maximum number of identical gift boxes that can be created such that each box contains items in exactly the same quantity from each type. This problem is solved by finding the greatest common divisor (GCD) of the given quantities.

Mathematically, if the quantities are \(q_1, q_2, \dots, q_n\), the maximum number of identical gift boxes is \(\gcd(q_1, q_2, \dots, q_n)\).

inputFormat

The input is given via stdin and consists of two lines. The first line contains a positive integer n, the number of different types of items. The second line contains n space-separated integers representing the quantities of each type.

outputFormat

Output via stdout a single integer: the maximum number of identical gift boxes that can be formed from the input quantities.

3
6 9 12

3