如您所知,在温暖的天气里,许多大城市的居民使用城市自行车共享服务。今天,阿尔卡迪将使用城市自行车从学校到家。
学校和房子位于同一条直街上,此外,同一条街上有n个可以租借或归还自行车的点。第一个自行车租赁点位于沿街道 x1 公里处,第二个位于 x2 点,依此类推,第 n 个自行车租赁点位于 xn 点。阿卡迪亚的学校位于点x1(即与第一个自行车租赁的同一地点),房子位于点xn(即与第n辆自行车租赁的同一地点)。已知对于所有 1 ≤ i < n,xi < xi + 1。
根据自行车租赁使用规则,阿尔卡迪只能在有限的时间内租用自行车,之后他必须将其归还到其中一个自行车租赁点,但他可以立即借用一辆新自行车,并且时间将重新开始倒计时。阿尔卡迪一次最多只能租一辆自行车。如果阿尔卡迪决定在某个租赁点骑自行车,那么他会归还他到达那里的自行车,只拿一辆新自行车并继续骑着它移动。
在规定的时间内,无论选择哪种自行车,Arkady 都能沿着街道行驶不超过 k 公里。
确定Arkady 是否能够骑自行车从学校到家,如果可以,他需要租用自行车的最少次数是多少次,包括第一辆自行车?请注意,阿尔卡迪今天不打算步行。
输入
第一行包含两个整数 n 和 k (2 ≤ n ≤ 1,000, 1 ≤ k ≤ 100,000) — 自行车租赁的数量以及 Arkady 可以骑一辆自行车行驶的最大距离。
下一行包含整数序列 x1, x2, ..., xn (0 ≤ x1 < x2 < ... < xn ≤ 100 000) - 自行车租赁点的坐标。确保自行车租赁的坐标按升序指定。
输出
如果 Arkady 无法仅骑自行车从学校回家,请打印 -1。否则,请打印 Arkady 需要在租赁点租赁的最少自行车数量。
示例
输入 #1
4 4 3 6 8 10
输出 #1
2
输入 #2
2 9 10 20
输出 #2
-1
输入 #3
12 3 4 6 7 9 10 11 13 15 17 18 20 21
输出 #3
6
注意
在第一个示例中,Arkady 必须从第一个自行车租赁处取出第一辆自行车并将其骑到第二个自行车租赁处。在第二个自行车租赁处,他必须带一辆新自行车,他可以用它去第四个自行车租赁处,他的房子就在旁边。因此,阿尔卡迪从学校到家只需要两辆自行车。
在第二个示例中,只有两辆自行车租赁,它们之间的距离是 10。但是一辆自行车可以行驶的最大距离是 9。因此,Arkady 将无法仅骑自行车从学校到家。