Minimum Path Cost in Array

You are given an array of non-negative integers. Each element in the array represents the cost to step onto that position. Starting at the first element, you can move forward either one step or two steps at a time. Your goal is to reach the end of the array while minimizing the total cost accumulated.

The cost to reach a position is defined as the sum of the cost at that position plus the minimal cost needed to get to one of the two previous positions. When you reach or pass the end of the array, you have completed the traversal.

Note: If the array contains only one element, then the answer is simply that element.

The recurrence relation for dynamic programming is given by:

$$\text{dp}[i] = \text{arr}[i] + \min(\text{dp}[i-1],\,\text{dp}[i-2]) $$

The final answer is the minimum between the last two computed values because the destination may be reached either by landing exactly on the last index or by skipping it.

inputFormat

The first line of input contains an integer n representing the number of elements in the array. The second line contains n space-separated integers representing the cost at each position in the array.

Constraints: 1 \( \leq n \leq 10^5 \), and each cost is a non-negative integer.

outputFormat

Output a single integer which is the minimum cost required to travel from the start to the end of the array.

## sample

3
10 15 20

15

</p>