An array \(a\) of \(n\) integers is given. Now write all possible permutations of the given array. For example, if the given array \(a = [2, 3, 6] \)and the permutations are \([2, 3, 6], [3, 6, 2], [6, 2, 3],...\)
So you will get \(n!\) arrays. In each of these arrays, you may perform the following operation at most once:

• You can select any subarray of length at most \(n - 2\) and replace all its values with a single integer. The chosen integer must be divisible by at least one number in the original array. For example, given the array \([2, 4, 6, 8],\) you could replace the subarray\( [4, 6]\) with \( 2 \) (resulting in \([2, 2, 2, 8]\)), but not with \(3\), as \(3\) is not divisible by any number in the array.

After all of the steps described above output the maximum GCD of the array among all possible permutations. 

The first line contains a single integer \(n \)- the number of array elements.
The next line contains \(n\) elements of the array.

\(3 \leq n \leq 10^6 \)
\(0 \leq a[i] \leq 10^6\)

Input copy	Output copy
5 2 3 8 19 4	4

One of the permutations of the given array is [8 4 3 19 2]. We can replace the subarray [3 19 2] with the value 4, so the final array would be [8 4 4 4 4]. The GCD of the final array is 4.