You find yourself in front of a long river and decide to cross it safely...
There are stones scattered throughout the river that you can jump on in order to make it to the other side. You start at position and the river ends at position .
From any given point, you can jump up to units forward, as long you don't land in the water. More specifically, you can jump on a stone at position if , where represents your current position.
Given the positions of the stones in no particular order, determine the minimum number of jumps needed for you to cross the river without coming into contact with water. If it is not possible for you to cross the river entirely, output
The first line of input contains space-separated integers, , , and .
The second line of input contains distinct integers representing , the position of each stone.
Output a single integer, the minimum number of jumps required (or
-1 if crossing the river is not possible).
Sample Input 1
5 12 3 2 4 5 10 7
Sample Output 1
Explanation for Sample 1
It is optimal to jump to the stone at position , followed by , , and . Then, you can make one final jump to the end of the river at position , safely making it across.
Sample Input 2
2 10 4 1 5
Sample Output 2
Explanation for Sample 2
You can jump to the stone at position followed by , however, you are unable to make the final jump from position to (since you can only jump up to units forward in this example).