亚历山德拉有一张纸条,上面有 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 在同一块上,因此不存在解决方案。