CF487B.Strip

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.

亚历山德拉有一条纸带，上面从左到右依次写着 $n$ 个数字，记为 $a_i$。

现在亚历山德拉想将这条纸带分割成若干段（可能只有一段）。每一段必须满足以下条件：

• 每段至少包含 $l$ 个数字；
• 每段中最大值与最小值之差至多为 $s$。

请帮助亚历山德拉找出满足上述条件的最少段数。

The first line contains three space-separated integers n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).

The second line contains n integers a__i separated by spaces ( - 109 ≤ a__i ≤ 109).

第一行包含三个以空格分隔的整数 $n$、$s$、$l$（$1 \leq n \leq 10^5$，$0 \leq s \leq 10^9$，$1 \leq l \leq 10^5$）。

第二行包含 $n$ 个以空格分隔的整数 $a_i$（$-10^9 \leq a_i \leq 10^9$）。

Output the minimal number of strip pieces.

If there are no ways to split the strip, output -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.

对于第一个样例，我们可以将纸条分割成 3 段：[1, 3, 1], [2, 4], [1, 2]。

对于第二个样例，我们不能让 1 和 100 出现在同一段中，因此不存在可行解。