P8940 [DTOI 2023] C. Missing Old Friend.

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.

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.

The first line contains two non-negative integers $n, k$. The second line contains $n$ numbers, representing $\{a_n\}$.

Output one number in one line, representing the answer.

#### 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: | Test Point ID | $n \leq$ | $k, a_i \leq$ | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^6$ | $10^9$ | All numbers are equal | | $2 \sim 4$ | $4$ | $10^9$ | None | | $5 \sim 8$ | $100$ | $10^9$ | None | | $9 \sim 12$ | $1000$ | $10^9$ | None | | $13 \sim 16$ | $10^6$ | $10^9$ | None | | $17 \sim 20$ | $4 \times 10^6$ | $10^9$ | None | 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