#P2110. 2024.9.21-JD-第1题-物品分组

2024.9.21-JD-第1题-物品分组

题目内容

有nn个物品，第ii个物品的价值为aia_i。

现在要给这些物品分组，每一组必须是一个下标连续的区间。

同时，每一组内的物品差距不能太大，即任意一组内物品的最大价值减去最小价值不能超过某个给定的常数kk。

给定这些物品，请问最少要分几组?

输入描述

第一行两个整数 n,k(1≤n≤105,0≤k≤109)n,k(1 ≤n≤ 10^5 ,0 ≤k≤ 10^9)，表示物品的数量及给定的常数。

第二行nn个整数 a(0≤ai≤109)a (0 ≤ a_i ≤ 10^9)，表示物品的价值。

输出描述

输出一行一个整数，表示最少的分组数。

样例1

输入

4 1
1 3 1 4

输出

4

说明

样例2

输入

4 2
1 3 1 4

输出

2

说明

知识点:*****

查看知识点以及同类型题目

Statistics