Mortal Kombat Tower

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ bosses in order; $a_i=0$ is easy and $a_i=1$ is hard. You and your friend alternate sessions, with your friend first. Each session kills 1 or 2 consecutive bosses. Your friend spends one skip point for each hard boss they kill; you spend none. Minimize the total skip points.

Input

Line 1 contains $n$. Line 2 contains binary values $a_1,\ldots,a_n$.

Output

Print the minimum number of skip points.

Subtasks

• Subtask 1 — 20 points: n <= 20.
• Subtask 2 — 30 points: n <= 5000.
• Subtask 3 — 50 points: 1 <= n <= 200000; a_i in {0,1}.

Examples

Input

8
1 0 1 1 0 1 1 1

Output

2

Explanation

An optimal schedule uses exactly 2 skip points: the friend pays for the first hard boss and the final hard boss while your sessions cover suitable hard blocks in between.