Frog Jump
By Giovanna Kobus Conrado, University of São Paulo 
Brazil
By Giovanna Kobus Conrado, University of São Paulo Brazil
A little flog wants to cross a river. Unfortunately the river might be too wide for the frog to cross it with only one jump. Fortunately, there are stones conveniently placed in a straight line that the frog can use to help it cross the river.
We will say the margin of the river the frog is currently placed in is located at 1 and that the other margin is placed at M. The N stones are located at S1, ... , Sn. The frog can make a jump between location i and location j if there is a margin or a stone in i and j and i < j. There is a limit for the size of the jump.
The frog can make two types of jumps: he can make a short jump from i to j if he can make a jump from i to j and the distance between them is no greater than X and he can make a long jump from i to j if he can make a jump from i to j and distance between them is no greater than Y.
If the frog makes two long jumps in a row his legs get sore and he might fall, so that needs to be avoided. You need to determine the minimum number of jumps needed for the frog to cross the river.
The first line of input contains two integers: N (0≤N≤106) and M (2≤M≤109) , the number of rocks and the location of the second margin of the river.
The second line of input contains N integers: the i-th integer is the location of the i-th rock (1<Si<M). The location of the rocks will be given in increasing order and it is guaranteed that all rock locations are different.
The third line of input contains two integers: X and Y (1≤X<Y≤109), the sizes of the short and the long jump.
The output must contain the minimum number of jumps needed for the frog to cross the river without making two long jumps in a row or -1 if it is impossible for the frog to cross the river.
| Input Sample | Output Sample |
|
3 6 |
3 |