ADACON - Ada and Connections

Ada the Ladybug was on a trip with her friends. They each bought a souvenir there. As all of them are mathematicians, everybody bought a number. They want to modify the numbers to have some connection between each other. They have decided to modify the numbers so they would have their GCD greater than 1 ( gcd(a1,a2,a3,...,aN)>1). Anyway it is not easy to change a number - the only thing they can do is to go to a professor in mathematics, which could forge a number A into number A+1 or A-1. As this operation is not cheap, they want to minimize number of such operations. A number might be forged any number of times.

NOTE: gcd(a,0)==a (so gcd of two 0 is also 0)

Input

The first line contains an integer 1 ≤ N ≤ 3*105, the number of friend who were on trip (and also the number of numbers).

The second line contains N integers 0 ≤ ai ≤ 106

Output

Print a single line with minimum number of operations to make a connection between all numbers.

Example Input

5
3 9 7 6 31

Example Output

2

Example Input 2

9
3 4 5 7 8 9 11 12 13

Example Output 2

6

Example Input 3

5
7 7 11 17 1

Example Output 3

5

Added by:Morass
Date:2017-06-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-12-31 20:28:33
@Rohit Agarwal you can add 1 to each number to make them all even and so gcd(array) = 2.

and to the others - Pi(10^6) (number of primes <= number on input) is ~78000, so that *N will surely get TLE.
2018-11-20 15:06:25 Rohit Agarwal
@morass: Could you please explain the last testcase? Why the answer is 5?

Last edit: 2018-11-20 16:36:41
2018-11-19 15:45:39 Rohit Agarwal
Getting WA, any testcases guys?
2018-09-05 16:37:21
is there a solution i am starting to get disinterested i got tle with java following @manya_cod4 tip but i think approach is different :(
@morass

Last edit: 2018-09-05 16:37:44
2018-09-04 19:09:22
hey can anyone tell me what is there complexity?
mine is n*(no. of prime number upto maximum no. of n)
because i got TLE for my solution....
2017-12-18 13:58:32
@morass what is the expected time complexity of this problem.? mine is n * (number of prime numbers upto largest number )
2017-06-23 02:00:27
I think it's my fault in misunderstanding the problem))) I was bound to guess that the solution must exist in any case. Meanwhile you could set one more problem (say ADACON0) with restricted rules for changing Ai ;)
2017-06-23 01:35:08
@feodorv: Even though it you passed a few test-cases :P Anyway sorry for unclear statement :/
2017-06-23 01:29:46
Oh, so i am solving other problem)))
2017-06-23 01:13:39
@feodorv: Oh yes, you can forge a number any number of times ^_^ I'll try to update statement to make it more clear :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.