← 返回题目列表

AtCoder · awc0087_c

C. 最短登山路线

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

分数: 366 分

问题陈述

高桥喜欢爬山,并正在计划穿越山脉的路线。山脉有 N 点排成一行,编号从 1 to N,以及每个点的高程 i (1 \leq i \leq N) 是 A_i 米。

Takahashi 选择一对整数 (l, r) 满意 1 \leq l \leq r \leq N,从点开始按顺序走一条经过每个点的路线 l 点 r 按其数字升序排列。该路线包含的点数为 r - l + 1.

的 总高程变化 该路线的 定义为沿途相邻点之间的绝对高差之和,即:

\sum_{i=l}^{r-1} |A_{i+1} - A_i|

请注意,当 l = r,这个总和是空总和,所以总的高程变化是 0.

高桥想要走一条总海拔变化至少为 K 用于培训目的。但是,由于时间有限,他想选择一条满足条件且包含的点数最少的路线。

如果一条路线的总海拔变化至少为 K 存在,求该路线中包含的最少点数。如果不存在这样的路由,则输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 0 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N K
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 表示点数和一个整数 K 表示总高程变化的下限,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个点的高程,以空格分隔。

输出

如果一条路线的总海拔变化至少为 K 存在,输出单行上该路线包含的最少点数。如果不存在这样的路由,则输出 -1.


示例输入 1

5 5
1 4 2 5 3

示例输出 1

3

示例输入 2

3 100
1 2 3

示例输出 2

-1

示例输入 3

10 15
0 10 3 8 1 9 2 7 4 6

示例输出 3

3

示例输入 4

20 500
0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100

示例输出 4

6

示例输入 5

1 1
1000000000

示例输出 5

-1