← 返回题目列表

Codeforces · 487/B

B. 条带

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

亚历山德拉有一张纸条,上面有 n 个数字。我们从左到右称它们为ai。

现在 Alexandra 想将其分成一些部分(可能是 1)。对于每一条条带,它必须满足:

- 每块应该至少包含 l 个数字。
- 棋子上的最大数字和最小数字之间的差异最多应为 s。

请帮助 Alexandra 找到满足上述条件的最少件数。

输入

第一行包含三个空格分隔的整数 n、s、l (1 ≤ n ≤ 105、0 ≤ s ≤ 109、1 ≤ l ≤ 105)。

第二行包含 n 个整数 ai,用空格分隔 (- 109 ≤ ai ≤ 109)。

输出

输出最少条数。

如果没有办法分割条带,则输出-1。

示例

输入 #1

7 2 2
1 3 1 2 4 1 2

输出 #1

3

输入 #2

7 2 2
1 100 1 100 1 100 1

输出 #2

-1

注意

对于第一个样本,我们可以将条带分成 3 块:[1, 3, 1]、[2, 4]、[1, 2]。

对于第二个样本,我们不能让 1 和 100 在同一块上,因此不存在解决方案。