Minimum Modifications to Form an Arithmetic Progression

You are given a sequence of n positive integers a₁, a₂, ..., a_n satisfying \(1 \le a_i \le w\). You are allowed to perform several modifications. In one modification, you can change any element of the sequence to any positive integer not exceeding \(w\).

Your task is to determine the minimum number of modifications required to transform the given sequence into an arithmetic progression with a non-negative common difference \(d \ge 0\). That is, after the modifications the sequence should become \(A, A+d, A+2d, \ldots, A+(n-1)d\) for some integer \(A\) and non-negative integer \(d\), with the additional constraint that \(A+(n-1)d \le w\) (so that all terms are \(\le w\)).

Note: The desired arithmetic progression is uniquely determined by its first term \(A\) and common difference \(d\) (with \(d \ge 0\)).

Hint: Consider for a fixed \(d\) the function \(A = a_i - (i-1)d\) for each position \(i\) and choose the best candidate \(A\) that requires the minimum number of modifications.

inputFormat

The first line contains two integers \(n\) and \(w\) (\(1 \le n \le 10^5\), \(1 \le w \le 10^9\)).

The second line contains \(n\) space-separated positive integers \(a_1, a_2, \ldots, a_n\) (each satisfying \(1 \le a_i \le w\)).

outputFormat

Output a single integer representing the minimum number of modifications required to transform the sequence into an arithmetic progression with a non-negative common difference.

sample

5 10
1 3 5 7 9

0