Implement a Convex Hull Tree.

JUST KIDDING.

Given an array of ~N~ positive integers, print the minimum GCD (greatest common divisor) of the numbers in any non-empty subarray and the maximum GCD of the numbers in any non-empty subarray.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 5000)~, the number of elements in the array.

The second line will contain ~N~ integers, the array, ~v_i\ (1 \le v_i \le 10^9)~.

Output Specification

On the first line, output the minimum GCD of the numbers in any non-empty subarray.

On the second line, output the maximum GCD of the numbers in any non-empty subarray.

Sample Input

4
2 4 3 6

Sample Output

1
6