题目描述

等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，这一常数称为公差。

特别地，只有一项的数列也是等差数列，此时我们认为公差为 0 。 给定一个有 项的正整数列 a1,a2,……an，满足 ai<=w。

你可以进行任意次修改，每次修改可以将数列的任意一项修改为任意<=w的正整数。

求至少进行多少次修改，可以使得原数列变成一个公差为非负整数的等差数列。

输入格式

第一行两个整数n,w(n>=1,w<=271828) 。 接下来一行n个整数 a1,a2,……an。

输出格式

一行一个整数，最小的修改次数。

输入输出样例

输入 #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

子任务 Subtask 1 (20分)：n=2,w=2 Subtask 2 (20分)：n,w<=100 Subtask 3 (10分)：ai=1 Subtask 4 (20分)：n,w<=1000 Subtask 5 (30分)：没有特殊限制。