当前没有测试数据。

题目描述

有 $N$ 个人站成一排拍照，从左到右依次编号为 $1$ 到 $N$。每个人都希望自己能被清楚地拍到，所以他们会调整自己的身高。第 $i$ 个人的身高为 $h_i$。

拍照时，每个人都会看向镜头。为了拍出一张好看的照片，摄影师要求：相邻两个人的身高差不能超过 $K$。也就是说，对于任意的 $i$（$1 \le i < N$），必须满足 $|h_i - h_{i+1}| \le K$。

现在给出每个人的初始身高，请问最少需要调整多少个人的身高，才能满足摄影师的要求？

每次调整可以选择任意一个人，将其身高调整为任意正整数。

输入格式

第一行包含两个整数 $N$ 和 $K$。

第二行包含 $N$ 个整数，表示每个人的初始身高。

输出格式

输出一个整数，表示最少需要调整的人数。

样例

输入

5 2
1 3 7 5 9

输出

2

数据范围

对于 $30\%$ 的数据，满足 $1 \le N \le 10$。

对于 $60\%$ 的数据，满足 $1 \le N \le 100$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le K \le 10^9$，$1 \le h_i \le 10^9$。