背景

等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，并称这个常数为公差。特别地，认为只有一项的数列也是等差数列，其公差视为 $0$。

题目描述

给定一包含 $n$ 项的正整数列 $a_1, a_2, \ldots , a_n$，满足 $1 \leq a_i \leq w$。

现可以进行若干次修改，一次修改可将数列的任意一项修改为任意 $\leq w$ 的正整数。

求：至少进行多少次修改，才能使得原数列变为一公差为非负整数的等差数列。

输入格式

第一行两个整数 $n, w$。
接下来一行 $n$ 个整数 $a_1, a_2, \ldots , a_n$。

输出格式

一行一个整数，所求答案。

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

提示

【样例解释 #1】

将 $a_3$ 修改为 $3$，$a_5$ 修改为 $5$。

【数据范围】

本题采用捆绑测试。

• Subtask 1（$20$ 分）：$n = 2$，$w = 2$。
• Subtask 2（$20$ 分）：$n, w \leq 100$。
• Subtask 3（$10$ 分）：$a_i = 1$。
• Subtask 4（$20$ 分）：$n, w \leq 1000$。
• Subtask 5（$30$ 分）：没有特殊限制。

对于 $100 \%$ 的数据，$1 \leq n, w \leq 3 \times 10^5$。

原始 idea：ix35。