← 返回题目列表

Codeforces · 587/A

A. 达夫和举重

中文机器翻译题面 查看原题

最近,达夫一直在练习举重。作为一次艰苦的练习,马雷克给了她一个任务。他给了她一系列的重量。其中第 i 个的重量为 2wi 磅。在每一步中,达夫都可以举起一些剩余的重物并将其扔掉。她这样做直到不再有重量为止。马利克要求她尽量减少步数。

Duff 是一位竞技编程爱好者。这就是为什么在每一步中,当且仅当存在一个非负整数 x 使得 2a1 + 2a2 + ... + 2ak = 2x, i 时,她只能举起并扔掉一系列权重 2a1, ..., 2ak。 e.这些数字的总和是 2 的幂。

Duff 是一位竞技编程爱好者,但不是程序员。这就是为什么她请求你的帮助。帮助她尽量减少步数。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 106),即权重的数量。

第二行包含 n 个整数 w1, ..., wn,用空格分隔(对于每个 1 ≤ i ≤ n,0 ≤ wi ≤ 106),2 的幂构成权重值。

输出

在一行中打印最少步数。

示例

输入 #1

5
1 1 2 3 3

输出 #1

2

输入 #2

4
0 1 2 3

输出 #2

4

注意

在第一个示例案例中:一个最佳方法是在第一步中丢弃前三个,在第二步中丢弃其余的。而且,不可能一步完成,因为它们的总和不是 2 的幂。

在第二个示例案例中:唯一的最佳方法是在每一步中扔掉一个重量。不可能用少于 4 个步骤来完成此任务,因为不存在超过一个权重且总和等于 2 的幂的权重子集。