← 返回题单

题单练习 ST表

← 上一题下一题 →

A6885 | $Strip$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Alexandra 有一条纸带，上面写有 $n$ 个数字。我们将这些数字从左到右分别记作 $a_{i}$。 现在，Alexandra 希望将这条纸带分割成若干段（也可以只分成一段）。对于每一段纸带，都必须满足下列条件： 每一段必须至少包含 $l$ 个数字。 每一段中的最大值与最小值之差不得超过 $s$。 请你帮助 Alexandra 找出满足上述条件所需的最少分段数。

输入格式

第一行包含三个用空格隔开的整数 $n, s, l\ (1\le n\le10^5, 0\le s\le10^9, 1\le l\le10^5)$。 第二行包含 $n$ 个用空格隔开的整数 $a_i\ (-10^9\le a_i\le10^9)$。

输出格式

输出满足条件的最少分段数。 如果无法分割纸带，则输出 $-1$。

输入输出样例

输入 #1

7 2 2
1 3 1 2 4 1 2

输出 #1

输入 #2

7 2 2
1 100 1 100 1 100 1

输出 #2

-1

C++ 编辑器

输入

输出