题目描述Description

在破除暗影刺客的诅咒后，伍六七失去了掌控魔刀千刃的能力，现在只能掌控他的理发剪刀

梅花十三让伍六七练习飞刀来练功以找回以前的功力，然而只想在小鸡岛和梅花十三好好过日子的阿七并不想练飞刀，但由于妻管严，阿七每天不情不愿地练习飞刀

受不了的阿七求十三能不能不练飞刀了，十三决定给阿七出一道题，如果阿七回答对了，就不让阿七练飞刀了

假设有 N(1 \leq N \leq 10 ^ 6) 个木桩，第i(1 \leq i \leq N)个木桩有a_i个桩节，现在阿七有不限次扔飞刀的次数，每次扔飞刀只能砍一个木桩，木桩每被砍一次就少一个桩节。每当木桩的桩节第一次达到 \lfloor \frac{a_i}{2} \rfloor 时，则会产生一次爆炸, 爆炸会让所有木桩少一个桩节，求阿七让所有木桩的桩节变为0的最少刀数

输入格式Input

第一行一个整数 N

第二行 N个整数 a_1,a_2,…,a_N

数据保证所有的 a_i 加起来不会超过 long long 范围，并且均为正整数

输出格式Output

一个整数，表示答案

样例Sample

提示Hint

对于最后一个样例的一个提示: 1变为0也会产生爆炸

出题Author

lxh

来源Source