Wasting time

Interview

Time limit1sMemory limit1024 MB

Summary

Find the longest time to first reach cell N from cell 1 when each cell's number sets the move length and at most two direction reversals are allowed.

Level: Medium5 of 10
Topics: Dynamic programming, Graph, Simulation
Solved: No attempts yet

Statement

Geondeok does not want to go to school, so he wants to arrive as late as possible. The route to school is a row of $N$ cells numbered from $1$ on the left to $N$ on the right. Geondeok starts on cell $1$ , and the school is on cell $N$ .

At the start, Geondeok faces the direction of the school. His commute works in an unusual way. Every minute, he moves in the direction he is facing by the number written on his current cell. He cannot move off the route.

Geondeok can reverse the direction he is facing at most twice. How many minutes after leaving does he reach the school cell for the first time if he delays that arrival as much as possible? Time spent reversing direction is ignored.

The first line contains the school cell number $N$ . $\left( 3\leq N\leq 200\,000 \right)$

The second line contains the integers $a_i$ written on each cell, separated by spaces. $\left( 0\leq a_i\leq 200\,000 \right)$

Input

The first line contains the school cell number $N$ . $\left( 3\leq N\leq 200\,000 \right)$

The second line contains the integers $a_i$ written on each cell, separated by spaces. $\left( 0\leq a_i\leq 200\,000 \right)$

Output

Print the number of minutes until Geondeok first reaches the school cell when he delays that arrival as much as possible. If there is no path that reaches the school, print $-1$ .

Examples4

Example 1
Input
```
5
3 1 2 1 1
```
Expected output
```
5
```
Example 2
Input
```
5
4 1 2 1 1
```
Expected output
```
1
```
Example 3
Input
```
3
1 2 1
```
Expected output
```
-1
```
Example 4
Input
```
9
1 2 2 4 2 1 1 1 1
```
Expected output
```
12
```