Background

An arithmetic sequence is a sequence where the difference between each term and the previous term is the same constant, known as the common difference. Notably, a sequence with only one term is also considered an arithmetic sequence, with the common difference considered as $0$.

Problem Description

Given a sequence of $n$ positive integers $a_1, a_2, \ldots, a_n$, where $1 \leq a_i \leq w$.

You can perform several modifications, where each modification can change any term in the sequence to any positive integer $\leq w$.

Determine the minimum number of modifications required to transform the original sequence into an arithmetic sequence with a non-negative common difference.

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

A single line containing an integer, the answer to the problem.

Sample Input and Output

Sample Input #1

6 1000
1 2 999 4 72 6

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Sample Input #3

1 1
1

Sample Output #3

0

Notes

[Sample Explanation #1]

Modify $a_3$ to $3$ and $a_5$ to $5$.

[Data Range]

This problem is bundled test cases.

• 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 restrictions.

For $100\%$ of the data, $1 \leq n, w \leq 3 \times 10^5$.

Original idea: ix35.

见题面 Input 部分

见题面 Output 部分