CF587A Duff and Weight Lifting

最近，Duff 一直在练习举重。作为艰苦的训练，Malek 给了她一个任务。他给了她一串杠铃。第 $i$ 个杠铃的重量为 $2^{w_{i}}$ 磅。在每一步中，Duff 可以举起剩下的一些杠铃，并把它们扔掉。她会一直这样做，直到没有杠铃剩下。Malek 让她尽量减少步数。  Duff 是一名竞赛编程爱好者。因此，在每一步中，她只能同时扔掉一组重量分别为 $2^{a_{1}},...,2^{a_{k}}$ 的杠铃，当且仅当存在一个非负整数 $x$，使得 $2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{k}}=2^{x}$，即这些杠铃的重量之和为某个二的幂。 Duff 是竞赛编程的粉丝，但她不是程序员。这就是为什么她请求你的帮助。请帮助她最小化所需的步骤数。

输入的第一行包含一个整数 $n$（$1\leq n \leq 10^{6}$），表示杠铃的数量。 第二行包含 $n$ 个用空格分隔的整数 $w_{1},...,w_{n}$（$0\leq w_{i}\leq 10^{6}$，$1\leq i \leq n$），表示每个杠铃重量的指数部分。

请输出一个整数，表示最少需要的步数。

在第一个样例中：一种最优方案是在第一步扔掉前三个杠铃，第二步扔掉剩下的所有杠铃。无法一步完成所有操作，因为它们的总重量不是二的幂。 在第二个样例中：最优方案只能每一步扔掉一个杠铃。无法在少于 4 步内完成，因为不存在某个重量为二的幂的子集包含超过一个杠铃。 由 ChatGPT 5 翻译