题目描述

塔子哥最近沉迷于一款割草游戏。所谓割草游戏，并不是割草模拟器，而是指一款击杀敌人快，很容易一次性就击杀大量敌人的游戏。

塔子哥每放一个大范围aoe技能下去，就能看见屏幕上一大片的敌人消失，非常解压。

这天，塔子哥又在玩这款割草游戏了，他看着面前的$n$个敌人，每个敌人都有$a_{i}$的血，但是突然发现他的技能只能给一个敌人造成$1$点伤害了。但好在塔子哥所使用的角色点了天赋，开局时给所有敌人添加debuff，当一名敌人血量降到一半及以下时，就会给所有敌人造成$1$点伤害(这个debuff触发一次后消失)。塔子哥想知道，他最少需要多少次攻击才能击杀所有敌人。

输入描述

第一行输入一个正整数$n$，代表敌人的最大数量

第二行输入$n$个正整数$a_i$，代表每个敌人的血量

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^9$

输出描述

一个正整数，代表塔子哥攻击的最小次数。

样例

输入

2
6 8

输出

10

说明

塔子哥打第一个敌人3次，触发天赋，每个敌人剩余2，7血。接下来，塔子哥打第二个敌人3次，触发天赋，每个敌人剩余1，3血。塔子哥无法再触发天赋了，因此还要攻击4次，总共是10次。

样例2

输入

4
1 2 4 4

输出

1