Background

Although luanmenglei is already a grown-up high school student, every time someone mentions luanmenglei's girlfriend from 8th grade, luanmenglei will sink into those wonderful memories and cannot pull himself out.

Problem Description

Given $n$, $k$, and a sequence $\{a_n\}$, you also have a temporary variable $x$. You may perform the following operation any number of times (possibly $0$ times). One operation works as follows:

1. Choose an interval $[l, r]$. For all $i \in [l, r]$, set $x \leftarrow \gcd(a_l, a_{l+1}, \cdots, a_r)$.
2. For all $i \in [l, r]$, set $a_i \leftarrow x$.

In short, each time you can choose an interval and change every number in it into the $\gcd$ of that interval.

The cost of one operation is $r - l + 1 + k$. Now you want to make every number in the sequence equal. Find the minimum total cost.

If you do not understand the meaning of $\gcd$ or multi-argument $\gcd$, you may refer to the following definition:

• $\gcd(a_1, a_2, \dots, a_k)$ means the greatest common divisor of $a_1, a_2, \dots, a_k$, i.e., the largest positive integer that can divide $a_1, a_2, \dots, a_k$ at the same time.

Input Format

The first line contains two non-negative integers $n, k$.

The second line contains $n$ numbers, representing $\{a_n\}$.

Output Format

Output one number in one line, representing the answer.

10 3
2 2 2 1 2 2 2 1 2 2 

13

10 0
2 2 2 1 2 2 2 1 2 3 

9

11 0
2 2 2 1 2 2 2 1 1 3 3 

10

Hint

Sample 1 Explanation.

Perform one operation and choose the interval $[1, 10]$.

Sample 4.

See old/old4.in and old/old4.out in the attached files.

This sample satisfies the constraints of test points $9 \sim 12$.

Sample 5.

See old/old5.in and old/old5.out in the attached files.

This sample satisfies the constraints of test points $13 \sim 16$.

Constraints and Hints.

For all data, it is guaranteed that $1 \leq n \leq 4 \times 10^6$, $0 \leq k \leq 10^9$, and $1 \leq a_i \leq 10^9$.

The specific limits for each test point are shown in the table below:

The input size of this problem is large. Please choose a fast input method. A suggested strategy is provided below:

Please add this line at the beginning of your code: std::ios::sync_with_stdio(false);std::cin.tie(0);.

Note that after adding this line, the efficiency of cin/cout will be greatly improved, ensuring that all data can be read within 250 ms. However, after using it you can only use cin/cout streams to read input.

Translated by ChatGPT 5