P7273 ix35's Arithmetic Progression.

An arithmetic progression is a sequence in which, starting from the second term, the difference between each term and the previous term is the same constant, and this constant is called the common difference. In particular, a sequence with only one term is also considered an arithmetic progression, and its common difference is regarded as $0$.

You are given a positive integer sequence $a_1, a_2, \ldots, a_n$ with $n$ terms, satisfying $1 \leq a_i \leq w$. You may perform some modifications. In one modification, you can change any term of the sequence to any positive integer $\leq w$. Find the minimum number of modifications needed to turn the original sequence into an arithmetic progression whose common difference is a non-negative integer.

The first line contains two integers $n, w$. The next line contains $n$ integers $a_1, a_2, \ldots, a_n$.

Output one integer on a single line, the required answer.

**Sample Explanation #1** Change $a_3$ to $3$, and change $a_5$ to $5$. --- **Constraints** **This problem uses bundled testdata.** - Subtask 1 ($20$ points): $n = 2$, $w = 2$. - Subtask 2 ($20$ points): $n, w \leq 100$. - Subtask 3 ($10$ points): $a_i = 1$. - Subtask 4 ($20$ points): $n, w \leq 1000$. - Subtask 5 ($30$ points): no special constraints. For $100\%$ of the testdata, $1 \leq n, w \leq 3 \times 10^5$. --- Original idea: ix35. Translated by ChatGPT 5