You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有一天，三人行团队不小心掉入了一个回合制游戏世界，只有通关才能回到 $sdnu$（可以不回去嘛），让人庆幸的是，这个游戏只有一关，就是把所有怪打完。

关卡中有 $n$ 个怪排成一排（别问为啥是一排，造物主这样规定的），$cjx$ 他们各有一个不同的技能效果。

$cjx$ 的技能是全体攻击，可以对所有怪物都造成一点伤害；

$swy$ 的技能是溅射伤害，可以对相邻的两个怪物都造成一点伤害（可以对尸体释放该技能）；

$wyk$ 的技能是单体伤害，可以对单个怪物造成一点伤害。

每个回合每人均可以释放一次技能。但是悲催的是每多加一回合都会让宿舍增加一点易燃点，$cjx$ 不想来一次火焰杯跨栏大赛，所以请帮助他们尽快结束这个关卡。

通俗来讲，就是击杀所有怪物最少需要多少回合

Input

第一行输入一个整数 $n$，代表关卡中怪物的总数。$(2 \le n \le 10^5)$

第二行输入$n$个正整数，$a_i$代表第$i$个怪物的血量$(1 \le a_i \le 10^9)$

Output

输出一个正整数 $ans$，即最少回合数。

Samples

4
3 4 8 10

4