Alexandra has a paper strip with
n numbers on it. Let's call them
ai 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个数字。让我们称呼他们ai从左到右。
现在亚历山德拉想把它分成几块（可能是 1 块）。对于每条，它必须满足：
-
每块应至少包含 l 个数字。
-
工件上最大数和最小数之差最多应为 s。
请帮助亚历山德拉找到满足上述条件的最小数量。
Output
Output the minimal number of strip pieces.
If there are no ways to split the strip, output -1.
Note
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.