Tháp Mortal Kombat (Mortal Kombat Tower)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ boss theo thứ tự; $a_i=0$ là dễ, $a_i=1$ là khó. Bạn và bạn của bạn luân phiên phiên chơi, bạn của bạn đi trước. Mỗi phiên phải hạ 1 hoặc 2 boss liên tiếp. Bạn của bạn tốn 1 skip point cho mỗi boss khó mà người đó hạ; bạn không tốn điểm. Hãy tối thiểu hóa tổng skip point.

Input

Dòng 1 chứa $n$. Dòng 2 chứa $n$ giá trị nhị phân $a_1,\ldots,a_n$.

Output

In số skip point nhỏ nhất.

Subtask

• Subtask 1 — 20 điểm: n <= 20. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: n <= 5000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= n <= 200000; a_i in {0,1}. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

8
1 0 1 1 0 1 1 1

Output

2

Giải thích

Một lịch tối ưu dùng đúng 2 skip point: bạn của bạn chịu boss khó đầu tiên và boss khó cuối cùng, còn bạn xử lý các cụm khó ở giữa khi thích hợp.