题目描述

给定一个长度为 $n$ 的数组，要求把数组分为若干部分，满足下面两个条件：

1. 每个部分至少含有 $l$ 个元素；
2. 每个部分中两两数的差值的最大值不超过 $s$。

问：在满足上述两个条件的情况下，数组最少能分成多少个部分？

输入格式

第一行三个整数 $n,s,l$，$1\le n,l\le 10^5$，$0\le s\le 10^9$。

第二行 $n$ 个整数 $a_i$，表示给定数组，$|a_i|\le 10^9$。

输出格式

输出一个整数表示答案，如果无解输出 $-1$。

7 2 2
1 3 1 2 4 1 2

3

7 2 2
1 100 1 100 1 100 1

-1