# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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?

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

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

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

Login to submit