241024 - 将数组之和减半的最小操作次数

题目描述

给你一个正整数数组 nums[] 。每一次操作中,你可以从数组中选择 任意 一个数并将它减小到 恰好 一半。(注意,在后续操作中你可以对减半过的数继续执行操作)

请你计算 将 nums[] 的数组和 至少 减少一半的 最少 操作数。

输入

第一行包含一个整数 n,表示数组中元素的个数。

第二行包含 n 个整数,表示数组中的每个元素。

输出

输出只有一行,包含一个整数 n,表示将 nums[] 的数组和 至少 减少一半的 最少 操作数

样例

输入

4
5 19 8 1

输出

3

输入

3
3 8 20

输出

3
说明

保证对于 100% 的数据满足:

1 <= n <= 10^5 , 1 <= nums[i] <= 10^7

提示:注意题目中加粗的关键描述。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 50
通过人数 30
金币数量 3 枚
难度 提高


上一题 下一题