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