A staircase has n stairs indexed 0 to n-1. Standing on stair i and taking a step charges you cost[i] (the toll is paid when you leave the stair, not when you arrive). From stair i a single step moves you to stair i+1 or stair i+2.
You may begin standing on either stair 0 or stair 1 (arriving there is free). The top is the position just past the last stair (index n). Return the minimum total toll to reach the top.
Input format
Line 1: an integer n, the number of stairs.
Line 2: n space-separated non-negative integers, cost[0..n-1].
Output format
A single integer: the minimum total toll to reach the top.
Constraints
- 2 <= n <= 100000
- 0 <= cost[i] <= 1000