Description

Little A is playing "Sword Immortal" (Jianxian). He encounters a Demon-Sealing Tower and wants to climb it from the outside.

The tower has $n$ floors; the height of floor $i$ is $h_i$. Little A starts on the ground. Climbing floor $i$ (that is, moving from floor $i-1$ to floor $i$) takes time equal to that floor’s height $h_i$. Little A can use "immortal arts" (xiān shù). Each time he uses it, he can jump up by one or two floors, and this process takes no time. However, after each jump, Little A will be exhausted and must climb at least one floor to rest before he can use the immortal arts to jump again.

Now Little A wants you to compute the minimal time to reach the top (floor $n$).

Input Format

The first line contains an integer $n$ representing the number of floors in the Demon-Sealing Tower.

The second line contains $n$ integers $h_i$ representing the height of the $i$-th floor from bottom to top.

Output Format

Output a single integer $t$, representing the minimal time.

5
3 5 1 8 4

1

Hint

For all testdata, it is guaranteed that $1 \le n \le 10^6$, $1 \le h_i \le 100$.

Translated by ChatGPT 5