#ABC019C. 潘多拉魔盒

潘多拉魔盒

题目描述:

AC君有一个潘多拉魔盒,每次往盒中放入一个物品贡献[灵气],魔盒会根据放入物品的灵气幻化一个独特的宝物,神奇的是灵气值为x的物品和灵气值为2x的物品幻化出的物品一定是相同的,现在AC君已知N个物品的灵气值,想知道魔盒可以幻化出多少种不同的宝物。

输入格式:

NN

a1 a2 ... aNa_1\ a_2\ ...\ a_N

其中a表示物品灵气值

输出格式:

一个整数表示答案

样例:

4
1 2 4 8
1
3
1 2 3
2

提示

对于50%的数据1<=N<=10001<=a<=10001<=N<=1000,1<=a<=1000

对于100%的数据1<=N<=1000001<=a<=1091<=N<=100000,1<=a<=10^9