ADACON - Ada and Connections

no tags 

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 sou 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 proffesor 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)


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


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

Example Input

3 9 7 6 31

Example Output


Example Input 2

3 4 5 7 8 9 11 12 13

Example Output 2


Example Input 3

7 7 11 17 1

Example Output 3


hide comments
feodorv: 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 ;)

morass: 2017-06-23 01:35:08

@feodorv: Even though it you passed a few test-cases :P Anyway sorry for unclear statement :/

feodorv: 2017-06-23 01:29:46

Oh, so i am solving other problem)))

morass: 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

feodorv: 2017-06-23 01:11:09

So we can change Ai to Ai+1 and then to Ai+2 and so on?

morass: 2017-06-23 00:33:29

@feodorv: Hello, for N==1, the answer is "the only element element" and gcd of two zero elements yield zero (according to mine definition). Thanks for asking ^_^

feodorv: 2017-06-22 23:29:54

What should we do if there are two zero elements in the number list?)
Or N == 1?

Last edit: 2017-06-23 00:01:20

Added by:morass
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)