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。