← 返回题目列表

AtCoder · awc0097_e

E. 山地徒步旅行

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥正计划在山区徒步旅行。

本课程包括 N 沿直线排列的点,以及点的高程 i (1 \leq i \leq N)是 H_i。高桥从点开始 1 并走到指定地点 N 通过点进行 1, 2, \ldots, N 按顺序。

高桥有恐高症,当从某个点移动时 i 来点 i+1 (1 \leq i \leq N-1),如果海拔降低了 K 或更多(也就是说,如果 H_i - H_{i+1} \geq K)。在任何其他动作中他都不会感到恐惧。

课程管理员可以选择任意数字(可能是 0) 来自点的点 2, 3, \ldots, N-1 并将它们的每个高度更改为任何非负整数值,以便高桥可以行走而不会感到恐惧。不同的点可以更改为不同的值,并且更改的值没有上限。然而,点的高程 1 和 N 无法更改。

找到需要更改高程的最少点数,以便高桥可以从该点步行 1 来点 N 从未感到恐惧。如果无论高程如何改变都无法避免恐惧,则输出 -1.

注意: 即使当 N \geq 3,答案可能是 -1。如果不变点之间的高程差 1 和 N 太大,无论中间点的高程如何改变,都无法避免恐惧。

约束

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入均为整数

输入

N K
H_1 H_2 \ldots H_N

第一行包含点数 N 和海拔下降阈值 K 触发恐惧,以空格分隔。第二行包含每个点的高程 H_1, H_2, \ldots, H_N,用空格分隔。

输出

在一行中打印需要更改高程的最少点数,以便高桥可以从该点步行 1 来点 N 从未感到恐惧。如果无法避免恐惧,就输出 -1.


示例输入 1

5 3
10 8 4 5 3

示例输出 1

1

示例输入 2

3 5
20 0 5

示例输出 2

-1

示例输入 3

12 4
15 13 9 12 8 6 10 5 4 7 3 2

示例输出 3

4

示例输入 4

30 7
100 95 90 82 85 78 70 72 65 60 54 58 50 49 42 35 38 31 25 20 23 18 12 10 5 8 3 2 1 0

示例输出 4

8

示例输入 5

2 1
0 0

示例输出 5

0