时间限制: 1000ms 空间限制: 262144kb

题目描述

在遥远的艾泽拉斯大陆，有个叫做闪金镇的地方最近经常受到邪恶的哥布林骚扰，伟大的人类战士“安度因·洛萨”决定率领暴风城军队前往闪金镇将他们全部消灭。 安度因·洛萨非常勇猛，他独自一人挑战了 n只哥布林，这些哥布林采取了站成一排的战术。安度因·洛萨的“顺劈斩”可以对最多连续 4 4只哥布林造成一点伤害（可以是一只，也可以是两只三只），当哥布林的生命值被减为 0时，它便会倒下，但是其尸体仍会占据一个位置（即不管哥布林是否倒下，都会占用顺劈斩的一个位置）。除了顺劈斩之外，他还拥有一招只能使用一次的绝技——“斩杀”，能够直接消灭连续的三只哥布林（也可以是一只或者两只）。安度因·洛萨为了节省自己的体力，想要知道他最少使用多少次顺劈斩才能够剿灭所有哥布林。

输入格式 第一行输入一个正整数 n，表示哥布林的数量。

第二行输入 n个整数，第 i个整数记为a[i] ，表示站成一排的哥布林中，第 i只哥布林的生命值。

输出格式 输出一个整数，表示安度因·洛萨最少需要使用顺劈斩的次数。

样例

Input 1 4

2 1 1 3

Output 1

2

Input 2

10 3 2 2 2 3 1 1 2 1 2

Output 2

5

数据范围 100%的数据，有1≤a[i]≤10^9,1≤n≤10^6