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.
Input format
Line 1: the integer n.
Line 2: n space-separated non-negative integers c[0] c[1] ... c[n-1].
Output format
A single integer: the minimum total toll to reach the platform beyond the last pylon.
Constraints
- 2 <= n <= 40
- 0 <= c[i] <= 999