No testdata at current.

盒子

时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

题目描述

小 $Y$ 有 $n$ 个盒子，第 $i$ 个盒子的大小是 $a[i]$，小 $Y$ 保证 $a[i]$ 一定是 $2$ 的若干次方，比如 $1, 2, 4, 8, 16, 32, 64, 128, 512, 1024\ldots$，一个大小为 $a[i]$ 的盒子的容量是 $a[i]/2$，就是说它可以装下总大小不超过 $a[i]/2$ 的其他盒子，特别地，大小为 $1$ 的盒子不能装下其他盒子。并且，装在盒子里的盒子也可以装其他盒子，比如，大小为 $8$ 的盒子可以装下一个大小为 $4$ 的盒子且大小为 $4$ 的盒子事先已经装了一个大小为 $2$ 的盒子。

现在小 $Y$ 想知道，最少能有多少个不被其他盒子装下的盒子？

输入格式

第一行 $1$ 个正整数 $n$，表示盒子的数量。

第二行 $n$ 个正整数 $a[i]$，表示每个盒子的大小，保证 $a[i]$ 一定是 $2$ 的若干次方。

输出格式

一行一个正整数表示最少能有多少个不被其他盒子装下的盒子。

输入输出样例

样例 1

输入：

5
1 2 1 1 8

输出：

1

说明： 图中盒子内部的灰色部分表示盒子不能用来装东西的一半容量，白色部分表示能用来装东西的一半容量，图中只有最大的盒子没有被装在其它盒子中，因此答案为1。

样例 2

输入：

3
1 1 1

输出：

3

样例 3

输入：

6
1 1 1 4 1 2

输出：

3

样例 4

输入：

3
8 4 2

输出：

1

数据范围与提示

本题共有 12 个测试点，每个测试点 10 分。

对于全部测试点：$1 \le n \le 100000$，$1 \le a[i] \le 2^{60}$

• 对于测试点 1-3：$1 \le n \le 3$
• 对于测试点 4-5：$1 \le a[i] \le 4$
• 对于测试点 6-9：$1 \le n \le 1000$

$2^{60} = 1152921504606846976$