思路：贪心

给定$n$个怪物，每次攻击能对一个敌人造成1点伤害，当一个敌人血量降到一半及以下时，会对所有敌人都造成一点伤害，求最少需要的攻击次数。

看完题面后，一个很直观的想法是，为了能尽量少的攻击，要将天赋效果尽可能发挥满。也就是说，如果一个敌人能被天赋效果aoe死，我们就不打他了。

而aoe触发次数是固定的n次，所以我们的任务就是决定怪物触发aoe的顺序，以及所有怪触发完aoe后的补刀。

题目描述

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

米小游每放一个大范围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