题目描述

有

nn个怪物排成一排，小红和队友们准备进攻这些怪物。 小红的技能是全体打击，对所有怪物造成 $1$ 点伤害。 队友 $1$ 的技能是单体打击，对单体怪物造成 $1$ 点伤害。 队友 $2$ 的技能是范围攻击，对相邻的两只怪物分别造成 $1$ 点伤害（可以对死去的怪物尸体释放该技能）。

每回合每个人均可释放 $1$ 次技能。小红想知道，击杀全部怪物最少需要多少回合？

输入格式

第一行输入一个正整数 $n$，代表怪物的总数。

第二行输入 $n$ 个正整数ai，代表每个怪物的血量。

$1<=ai<=109$

$2<=n<=105$

输出格式

一个整数，代表击杀全部怪物的最少回合数

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

2

提示

样例解释： 第一回合，小红攻击全体怪物，队友 $1$ 攻击 $5$ 号怪物，队友 $2$ 攻击 $4$ 号和 $5$ 号怪物，剩余每只怪物血量为[$0$,$1$,$2$,$2$,$2$]。 第二回合，小红攻击全体怪物，队友 $1$ 攻击 $5$ 号怪物，队友 $2$ 攻击 $3$ 号和 $4$ 号怪物，即可击杀所有怪物。