ix35 的等差数列

题目背景

等差数列是指从第二项起,每一项与它的前一项的差等于同一个常数的一种数列,并称这个常数为公差。特别地,认为只有一项的数列也是等差数列,其公差视为 $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$。

输出格式


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

输入输出样例

输入样例 #1

6 1000
1 2 999 4 72 6

输出样例 #1

2

输入样例 #2

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

输出样例 #2

3

输入样例 #3

1 1
1

输出样例 #3

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。