401. Cheapest Way Up
Each step of a staircase charges a toll. You are given n tolls, one per
step.
You may begin at step 0 or at step 1. From a step you pay its toll and then climb either one step or two. Reaching past the last step is the top.
Print the smallest total toll you can pay.
Note what changed from counting: there is no longer one answer per route to add up, there is a best route to find. The two branches are combined with a minimum instead of a sum, and everything else about the shape is the same.
Constraints - `2 ≤ n ≤ 100000` - `0 ≤ cost[i] ≤ 1000`
Input
The first line contains an integer n.
The second line contains n space-separated integers, the toll on each step.
Output
Print one integer: the smallest total toll paid to get past the last step.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.