Minimum GCD Operations to Equalize Array

You are given an array of integers. In one operation, you can choose any pair of adjacent elements in the array and replace both of them with their greatest common divisor (\(\gcd(x,y)\))).

Your task is to determine the minimum number of operations required to make all the elements of the array equal. If the array already consists of identical elements (i.e. every element is equal to the \(\gcd\) of the entire array), then no operation is needed.

Note: When transforming the array, if it is not already uniform, the minimum number of operations required will always be n - 1 where n is the number of elements in the array.

For example:

• For the array \([12, 15, 18]\), the answer is 2.
• For the array \([5, 5, 5, 5]\), the answer is 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
a1 a2 a3 ... an

where n is the number of elements in the array and a1, a2, ..., an are the integers in the array.

outputFormat

The output is a single integer written to standard output (stdout) representing the minimum number of operations required to make all elements of the array equal.

## sample

3
12 15 18

2