CF910A The Way to Home

A frog lives on the axis $ Ox $ and needs to reach home which is in the point $ n $ . She starts from the point $ 1 $ . The frog can jump to the right at a distance not more than $ d $ . So, after she jumped from the point $ x $ she can reach the point $ x+a $ , where $ a $ is an integer from $ 1 $ to $ d $ . For each point from $ 1 $ to $ n $ is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points $ 1 $ and $ n $ . Determine the minimal number of jumps that the frog needs to reach home which is in the point $ n $ from the point $ 1 $ . Consider that initially the frog is in the point $ 1 $ . If the frog can not reach home, print -1.

N/A

N/A

In the first example the from can reach home in two jumps: the first jump from the point $ 1 $ to the point $ 4 $ (the length of the jump is three), and the second jump from the point $ 4 $ to the point $ 8 $ (the length of the jump is four). In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.