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.

Add +1 using 1 gold coin

Add -1 using 1 gold coin

Leave the element as it is

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

1 ≤ N ≤ 10^5

2 ≤ Ai ≤ 10^6

Output

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

Samples

Input

Output

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.

Input

Output

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.