Remove Element to Maximize GCD

You are given an array of integers. Your task is to remove exactly one element from the array such that the greatest common divisor (denoted as \(\gcd\)) of the remaining elements is maximized. If there are multiple choices that yield the same maximum \(\gcd\), you must remove the smallest element among those candidates.

For example:

• For the array [2, 6, 8, 3], removing 3 yields the maximum \(\gcd\) of the remaining elements.
• For the array [7, 7, 7, 7], removing any element results in \(\gcd = 7\), so the smallest element (7) is chosen.

Note: The \(\gcd\) of a set of numbers is defined as the largest positive integer that divides each of the numbers without leaving a remainder.

inputFormat

The input is given from standard input (stdin) and is structured as follows:

1. The first line contains an integer \(n\) (\(n \geq 2\)), representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer: the smallest element that can be removed to maximize the \(\gcd\) of the remaining elements, printed to standard output (stdout).

4
2 6 8 3

3