Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Strip

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlexandra 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.

Examples

Input

7 2 2

1 3 1 2 4 1 2

Output

3

Input

7 2 2

1 100 1 100 1 100 1

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 12:54:08 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|