Remove One for the Greatest GCD

If an integer A is divisible by B, then B is a divisor of A and A is a multiple of B.

The greatest common divisor of several integers is the largest of their common divisors. For example, the common divisors of 12 and 8 are 1, 2, and 4, so the greatest common divisor of 12 and 8 is 4.

You remove one number K from N integers and want the greatest common divisor of the remaining N-1 numbers to be as large as possible. The greatest common divisor of the remaining numbers must not be a divisor of K.

For example, if you remove 8 from 8, 12, 24, 36, 48, the greatest common divisor of the remaining 12, 24, 36, 48 is 12. Since 12 is not a divisor of the removed number 8, this is a valid answer. Removing any other number cannot make the greatest common divisor larger than 12.

For 8, 12, 20, 32, 36, however, whichever number you remove, the greatest common divisor of the remaining numbers is a divisor of the removed number, so there is no answer.

Given N numbers, write a program that finds the largest greatest common divisor you can obtain by removing one integer.

The first line contains the number of integers N. ($4 \le N \le 1\,000\,000$)

Then N numbers follow, separated by spaces or newlines. Each number is a positive integer not exceeding $2\,000\,000\,000$.

On the first line, print the largest greatest common divisor you can obtain by removing one integer, then a single space, then the removed number.

If the removed number is K, the greatest common divisor of the remaining numbers must not be a divisor of K.

If no valid removal exists, print -1.