Remove One for the Greatest GCD

Time limit2sMemory limit512 MB

Summary

Remove one number so the GCD of the rest is as large as possible, but that GCD must not divide the removed number.

Level: Medium7 of 10
Topics: Number theory, Prefix sum, Greedy
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples2

Example 1
Input
```
5
8 12 24 36 48
```
Expected output
```
12 8
```
Example 2
Input
```
5
8 12 20 32 36
```
Expected output
```
-1
```