Climbing the Demon Tower

Little A is playing "Sword Immortal" and has encountered a demon-lock tower. The tower has \(n\) floors with the height of the \(i\)-th floor given as \(h_i\). Little A can use his mystical skills to jump up either 1 or 2 floors at a time. However, after every jump he becomes exhausted and must climb at least one floor normally to regain his strength before he can jump again (you may assume that Little A essentially needs to perform a normal climb after each jump).

Your task is to determine the minimum time required for Little A to reach the top of the tower. When climbing normally, the time taken is equal to the height of that floor, \(h_i\). Jumping, on the other hand, does not require extra time. Note that after a jump, the next move must be a normal climb.

Hint: Use dynamic programming with two states: one where a jump can be performed and one where a normal climb is forced.

inputFormat

The input begins with a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of floors. The next line contains \(n\) space-separated integers \(h_1, h_2, \ldots, h_n\) (\(1 \leq h_i \leq 10^9\)), where \(h_i\) is the height of the \(i\)-th floor.

outputFormat

Output a single integer, the minimum time required for Little A to reach the top (floor \(n\)).

sample

3
1 2 3

2