哈尔的移动（与喵喵）城堡

哈尔的移动城堡目前正在进行翻修，城堡的墙壁正变得更加锋利和清晰。

城堡的状态可以用一个数字来描述，初始时为 $0$。城堡可以经历 $N$ 种不同的工序，每种工序都可以用一个非负整数 $a_i$ 来表示。当使用工序 $i$ 时，哈尔可以将城堡的状态数字加上或减去 $a_i$，只要状态数字保持非负即可。哈尔可以选择使用哪些工序、如何使用它们，以及它们的使用顺序。每种工序最多只能使用一次。

自然地，城堡状态数字的二进制表示中的每个 $1$ 都代表墙上的一个凸起，这是一个缺陷。因此，哈尔试图最小化缺陷的数量，换句话说，就是最小化其状态数字二进制表示中 $1$ 的个数。

然而，作为强制性月度维护指标的一部分，城堡必须经历至少一个工序。在满足这些约束条件的前提下，求城堡可能拥有的最少缺陷数量。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示不同工序的数量。

接下来有 $N$ 行，其中第 $i$ 行包含一个整数 $a_i$ ($0 \le a_i \le 10^6$)，表示工序 $i$ 对城堡状态数字的修改量。

输出格式

输出一个整数，表示在城堡必须经历至少一个工序的约束下，城堡可能拥有的最少缺陷数量。

样例

样例输入 1

4
39 15 30 27

样例输出 1

2