A maintenance gondola climbs a line of n service pylons numbered 0 to n-1. Stepping onto pylon i charges a toll c[i]. From a pylon you may advance either 1 or 2 pylons ahead. The gondola may begin by stepping onto either pylon 0 or pylon 1 (paying that pylon's toll). The destination is the platform just beyond the last pylon, i.e. you finish as soon as you step past pylon n-1.
Find the minimum total toll to reach the top platform.
Line 1: the integer n.
Line 2: n space-separated non-negative integers c[0] c[1] ... c[n-1].
A single integer: the minimum total toll to reach the platform beyond the last pylon.
Example 1
Input
3 10 15 20
Expected
15
Explanation
Start on pylon 1 (toll 15) and take a 2-step to move past pylon 2 to the platform. Total toll 15.
Example 2
Input
4 0 2 2 1
Expected
2
Explanation
Start on pylon 0 (0), step to pylon 2 (2), then step past pylon 3. Total 2, and no cheaper route exists.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →