Strip

给定一个长度为 $n$ 的数组，要求把数组分为若干部分，满足下面两个条件： 1. 每个部分至少含有 $l$ 个元素； 2. 每个部分中两两数的差值的最大值不超过 $s$。 问：在满足上述两个条件的情况下，数组最少能分成多少个部分？ $1\le n,l\le 10^5,1\le s\le 10^9, \forall 1\le i\le n, -10^9\le a_i\le 10^9$。

Alexandra has a paper strip with $ n $ numbers on it. Let's call them $ a_{i} $ from left to right. Now Alexandra wants to split it into some pieces (possibly $ 1 $ ). For each piece of strip, it must satisfy: - Each piece should contain at least $ l $ numbers. - The difference between the maximal and the minimal number on the piece should be at most $ s $ . Please help Alexandra to find the minimal number of pieces meeting the condition above.

The first line contains three space-separated integers $n,s,l (1\le n\le10^5, 0\le s\le10^9, 1\le l\le10^5)$. The second line contains $n$ integers $a_i$ separated by spaces $(-10^9\le a_i\le10^9)$.

Output the minimal number of strip pieces. If there are no ways to split the strip, output -1.

7 2 2
1 3 1 2 4 1 2

3

7 2 2
1 100 1 100 1 100 1

-1

For the first sample, we can split the strip into $3$ pieces: $[1,3,1], [2,4], [1,2]$. For the second sample, we can't let $1$ and $100$ be on the same piece, so no solution exists.