# 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