Background

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$.

Problem Description

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.

Input Format

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

Output Format

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

6 1000
1 2 999 4 72 6

2

10 2
2 1 2 2 1 1 2 2 2 2

3

1 1
1

0

Hint

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