Transform the Sequence via GCD Operations

You are given an integer n, an integer constant k, and a sequence \(\{a_i\}_{i=1}^n\). You also maintain a temporary variable \(x\). You are allowed to perform the following operation any number of times (possibly 0):

1. Select an interval \([l, r]\) (1-indexed). Compute \[ x = \gcd(a_l, a_{l+1}, \dots, a_r), \] where \(\gcd(a_1,a_2,\dots,a_m)\) denotes the greatest common divisor of \(a_1,a_2,\dots,a_m\).
2. Then, for every index \(i\) with \(l \le i \le r\), update \(a_i \leftarrow x\).

The cost of performing an operation on the interval \([l, r]\) is

[ (r-l+1) + k. ]

Your goal is to make all elements of the sequence equal (that is, the sequence becomes (c, c, \dots, c) for some integer (c)). It can be proved that if it is possible at all, then the only candidate for (c) is the overall greatest common divisor of the original sequence, namely

[ G = \gcd(a_1, a_2, \dots, a_n). ]

Find the minimum total cost required to achieve this transformation.

Note: If the sequence is already uniform, the cost is 0.

inputFormat

The first line contains two integers n and k separated by a space.

The second line contains n positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

It is guaranteed that \(a_i\) are positive integers.

outputFormat

Output a single integer representing the minimum total cost to convert the sequence so that all elements are equal to \(G = \gcd(a_1, a_2, \dots, a_n)\).

sample

3 5
1 1 1

0