678. The Stairs Game

0

Easy

Given an integer array cost, where cost[i] represents the cost of the ith step on a staircase. After paying the cost, you can climb either one or two steps.
You can start from either the step with index 0 or the step with index 1.
Help find the minimum cost to reach the top of the staircase. Print the minimum cost.

Input Format

The first line contains N, the size of the array.

The second line contains the array elements.

The second line contains the array elements.

Output Format

Print the minimum cost to reach the top of the staircase.

Example

Input

3
10 15 20

Output

15

Constraints

2 <= cost.length <= 1000

0 <= cost[i] <= 999

0 <= cost[i] <= 999

Loading...

View Submissions

Console