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.

Input

The first line contains three space-separated integers $*n*, *s*, *l*$ ($1 ≤ *n* ≤ 10^{5}, 0 ≤ *s* ≤ 10^{9}, 1 ≤ *l* ≤ 10^{5}$).

The second line contains $*n*$ integers $*a*_{*i*}$ separated by spaces ($- 10^{9} ≤ *a*_{*i*} ≤ 10^{9}$).

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.