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.


    Discussion

    Statistics


    76% Solution Ratio

    alamkhanEarliest, 1M ago

    TurinhstuFastest, 0.0s

    steinumLightest, 393 kB

    steinumShortest, 669B

    Submit

    Login to submit