买来了个魔法弹珠,想做一个游戏。 魔法弹珠有一个特点,如果两枚魔法弹珠相互碰撞,较小的一枚会被较大的一枚吸收,较大的那枚的体积就会变成两枚弹珠的体积之和,如果两枚弹珠体积相同,则两枚弹珠被吸收的概率相同。 这个游戏就是,把弹珠全都放到一个桶里,然后摇摇摇......直到剩下最后一枚弹珠。 那么剩下的最后一个弹珠可能有几种情况呢? 枚弹珠的编号各自是互不相同的,但体积可能一样。 两种游戏结果不同当且仅当最后剩余的弹珠编号不同。
输入描述:
第一行一个整数第二行个整数表示个弹珠的体积 弹珠体积


输出描述:
输出一个整数表示答案。
示例1

输入

4
6 6 2 3

输出

2

说明

多次碰撞后,剩下的最后一颗弹珠体积是17,一定是最开始体积为6的弹珠变成的。但是有2颗不同编号为6的弹珠,所以我们输出2
加载中...