GCD Challenge

Limits 1s, 512 MB

Shoaib and Alam are good friends. They love to challenge each other with programming and mathematical problems. One day Shoaib gives Alam this recursive function F and an array A (1 indexed) of length N.

function F(i)
    if (i <= 0) return 0

    value1 = F(i - 1)
    value2 = GCD(A[i], F(i - 1))

    return GCD(value1, value2)

Where GCD(x,y) function returns the Greatest Common Divisor(GCD) of x and y.

He also gives Alam some flexibility which Alam can use by spending some gold coins. For each element of the array A, Alam can perform any 1 of this 3 operations once.

Now Alam has to find the maximum possible value of F(N) and minimum number of gold coins to achieve that maximum F(N). Can you help him to find it?

Input

The first line of input contains an integer N which is the number of elements in array A.

The next line contains N integers Ai, elements of the array A.

Constraints

Output

Print the maximum possible F(N) and minimum number of gold coins to achieve that maximum F(N).

Samples

InputOutput
3
4 5 6

5 2

A[1]: Add +1 using 1 gold coin

A[2]: Leave it as it is

A[3]: Add -1 using 1 gold coin

So the array becomes,

5 5 5

For this new array, F(3) = 5. It is the maximum possible F(3). And minimum number of gold coins required to achieve this was 2.

InputOutput
1
2

3 1

A[1]: Add +1 using 1 gold coin

So the array becomes,

3

For this new array, F(1) = 3. It is the maximum possible F(1). And minimum number of gold coins required to achieve this was 1.