Problem2534--平安夜减肥!

2534: 平安夜减肥!

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 40  Solved: 13
[Submit] [Status] [Web Board] [Creator:]

Description

最近,Lx一直处于在减肥的状态,所以都把好看的哆啦A梦的头像换成了一只肥猫的头像,直到减肥成功才换回来!减肥的过程是艰苦的,大龙给了他一个任务,给了一个堆重量的哑铃。其中第i个重量是2ai磅的哑铃,在每个步骤中,Lx都可以提起一些剩余的哑铃并将其扔掉,直到没有重复的重量。大龙就是用哑铃这个方法瘦下来成现在这个身材的!

在每一步中,只有当存在一个非负整数使得2a1+2a2+....+2ak=2x时,Lx才能丢弃重量为2a1....2ak的哑铃

Lx已经处于减肥无法自拔,想减肥成功去追他喜欢的那个她,所以被减肥冲昏头脑的Lx现在来求助你,需要你帮他计算最少的步数

Input

测试数据有多组。

对于每组测试数据第一行有一个整数n(1<=100000)表示有n个哑铃

第二行输入n个数,表示每个哑铃ai的重量(0 <= ai <= n)

Output

输出扔掉后所需最少的步数

Sample Input Copy

5
1 1 2 3 3
4
0 1 2 3

Sample Output Copy

2
4

HINT

养了一身的膘,不减了不减了hhhhhhhhh

Source/Category