问题描述

在三国无双的战场上，Dash 是一名勇猛的将军。他挥舞着大刀，面对着无数敌军。每当他使出一个强大的范围技能，敌军就像稻草一样倒下，瞬间清空一大片，令人热血沸腾。

然而，这一次战斗的形势有些不同。面前有 $n$ 个敌将，每个敌将的生命值为 $a_i$。更糟糕的是，Dash 发现他的技能只能对一个敌将造成 $1$ 点伤害。不过，幸运的是，Dash 有一个特殊技能旋风斩：当某个敌将的生命值降至一半或以下时，这个技能会触发，对所有敌将造成 $1$ 点伤害（每个敌将只会触发一次）。

现在，Dash 需要知道，他最少需要多少次攻击才能击败所有的敌将，彻底扫平战场。

输入格式

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

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

输出格式

输出一个正整数，代表最小攻击次数。

样例

2
4 1

2

解释 #1

攻击两次血量为 $4$ 的敌将，触发一次debuff，血量为 $1$ 的敌将的debuff也被触发。

4
2 5 5 7

6

数据范围

• $1\leq n \leq 10^5$
• $1\leq a_i \leq 10^9$