541. Peter's Treasure Hunt

0

Hard

Peter resides in a neighboring kingdom close to Slovakia. One day, he embarks on a treasure hunt and possesses a map that displays the kingdoms and their relative positions from Peter's homeland.
The map consists of N+1 kingdoms located at points [0, 1, ..., N]. Each kingdom contains treasure, and all kingdoms are equipped with a special type of teleporter. The power of each teleporter is denoted by A[i]. By utilizing a teleporter with power A[i], Peter can collect treasure from the kingdoms located within the range [i - A[i], i + A[i]].
Your task is to determine the minimum number of teleporters Peter needs to use in order to collect treasures from all the kingdoms. If it is impossible to collect treasures from all the kingdoms, output '-1'.

Input Format

The first line of input consists of two integers N (1 ≤ N ≤ 1e4).
The second line of input consists of N+1 integers A[0],A[1],…,A[n-1],A[n] (0 ≤ A[i] ≤ 100), where Ai represents the power of the teleporter.

Output Format

Print the minimum number of teleporters Peter needs to use in order to collect treasures from all the kingdoms. If it is impossible, print '-1'.

Example

Input

Output

Constraints

(1 ≤ N ≤ 1e4)

A[0],A[1],…,A[n-1] , A[n] ( 0 ≤ A[i] ≤ 100)

A[0],A[1],…,A[n-1] , A[n] ( 0 ≤ A[i] ≤ 100)

Loading...

View Submissions

Console