Staircase with a cost

You’re climbing a staircase with n stairs. On each step, you can either climb 2 stairs or climb only 1. As you step on each stair, you pay a cost associated with that stair. Your task is to climb to the very top by paying as little as possible.

Input

The first line of the input contains a single integer n (1 ≀ n ≀ 1000).
The next line contains the costs associated with each stair (0 ≀ ≀ 1000).

Output

The program should print the minimum cost to reach the top of the staircase.

Examples

Input
Output
3 10 12 25
12
10 1 20 1 1 1 20 1 2 20 1
7

Explanation

  1. We stand in front of the staircase β‡’ the current cost is 0. We step on the second staircase β‡’ the cost is 12. Then we get out of the staircase by doing a step of length 2 β‡’ cost remains 12.
  1. 1 20 1 1 1 20 1 2 20 1 β‡’ 1 20 1 1 1 20 1 2 20 1 β‡’ 1 20 1 1 1 20 1 2 20 1 β‡’ 1 20 1 1 1 20 1 2 20 1 β‡’ 1 20 1 1 1 20 1 2 20 1 β‡’ 1 20 1 1 1 20 1 2 20 1 β‡’ 1 20 1 1 1 20 1 2 20 1 β‡’ 7
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue