Minimize Maximum Element

You are given an array of n positive integers. You are allowed to perform several operations on the array. In each operation, you may choose a pair of elements and perform an operation that effectively equalizes or reduces the maximum element of the array. It turns out that the optimal strategy will always allow you to reduce the maximum element to the greatest common divisor (GCD) of all elements in the array.

Task: Compute the minimum possible value of the maximum element in the array after any number of allowed operations. Mathematically, if the array is \(a_1, a_2, \dots, a_n\), then you must output \(\gcd(a_1, a_2, \dots, a_n)\).

Note: For a single element array, the answer is the element itself.

inputFormat

The input is given via standard input and consists of two lines. The first line contains a single integer \(n\) representing the size of the array. The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output via standard output a single integer, which is the greatest common divisor of the array, i.e. the minimum possible value of the maximum element after performing the operations.

3
5 9 12

1