47. Jump Game

Difficulty: medium · Array, Greedy

Problem

You are standing at the first index of an array of non-negative integers. Each element is the **maximum** number of steps you may jump forward from that position (you may also jump fewer steps). Print `true` if you can reach the last index, otherwise `false`.

Input

A single line containing the array elements separated by single spaces.

Output

Print `true` or `false`.

Example 1

Input:
2 3 1 1 4
Output:
true

Explanation: Jump 1 step to index 1, then 3 steps to the last index.

Example 2

Input:
3 2 1 0 4
Output:
false

Explanation: Every route lands on index 3, whose value is 0, so the last index cannot be reached.

Constraints

- 1 <= number of elements <= 10^5 - 0 <= each element <= 10^5

Solutions are judged against 2 sample and 10 hidden tests. Sign in to solve it · All problems