Minimum Numbers to Add for GCD One

You are given an array of n non-negative integers in non-decreasing order. Your task is to determine the minimum number of integers you must add to the array so that the greatest common divisor (GCD) of all the integers in the array becomes 1.

Recall that the GCD of a set of integers \(a_1, a_2, \dots, a_n\) is defined as:

[ \gcd(a_1, a_2, \dots, a_n)]

If the current GCD of the array is 1, then no additional numbers are needed. Otherwise, adding just one appropriate number will always be sufficient to make the GCD 1. Your program should read the input from standard input and write the result to standard output.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), which is the number of elements in the array. The second line contains n non-negative integers, provided in non-decreasing order, separated by spaces.

outputFormat

Output a single integer representing the minimum number of integers that must be added to the array so that its GCD becomes 1.

3
2 4 8

1