Minimum Jumps to End

You are given an array of non-negative integers where each element represents the maximum jump length at that position. Your task is to determine the minimum number of jumps required to reach the last index of the array. If it is not possible to reach the end, output -1.

Formally, given an array \(A\) of length \(n\), find the minimum number \(k\) such that there exists a sequence of indices \(i_0, i_1, \dots, i_k\) with \(i_0 = 0\) and \(i_k = n-1\) and for each \(0 \leq j < k\), \(i_{j+1} - i_j \leq A[i_j]\). If no such sequence exists, output -1.

This problem encourages the use of a greedy strategy to achieve an optimal solution in linear time.

inputFormat

The first line of input contains an integer \(n\) (1 \(\leq n \leq\) 10⁵) representing the number of elements in the array.

The second line contains \(n\) space-separated integers \(A[i]\) (0 \(\leq A[i] \leq\) 10⁵) where each integer denotes the maximum jump length from that index.

outputFormat

Output a single integer: the minimum number of jumps required to reach the last index. If it is not possible to reach the last index, output -1.

## sample

5
2 3 1 1 4

2

</p>