Practice on Toph

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

GCD Challenge

By Taran106 · 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.

• 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

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.

Statistics

76% Solution Ratio

alamkhanEarliest, Dec '20

TurinhstuFastest, 0.0s

steinumLightest, 393 kB

steinumShortest, 669B

Related Contests

 AUST Game of Codes - Fall 2019 Sep '20 Replay of AUST Game of Codes - Fall 2019 Dec '20