Frog Crossing

A frog wants to cross a river by hopping along a line of stones. stones lists the positions of the stones in increasing order. The first stone is at position 0, where the frog sits, and the last stone is on the far bank. The frog can land only on stones, never in the water, and it always jumps forwards.

Its first jump must be exactly 1 unit long. After a jump of k units, its next jump must be k - 1, k or k + 1 units long, and never 0.

Write can_cross(stones) that returns True if the frog can reach the last stone, and False otherwise.

Examples

can_cross([0, 1, 3, 6, 10])  # returns True
can_cross([0, 1, 3, 4, 8])   # returns False
can_cross([0, 2])            # returns False

In the first example the jumps are 1, 2, 3 and 4 units long. In the last one the first jump of 1 unit lands in the water.

Constraints

• 1 <= len(stones) <= 600
• stones[0] == 0 and the positions strictly increase, up to 10**9.

Note

With only one stone, the frog is already on the far bank.