分数: 400 点
问题陈述
发现蛇核 N 奇怪的生物。 每个生物都有固定的颜色和大小。颜色和尺寸 i-th 生物由 i 和 A_i。
每个生物都可以吸收另一个体型至多是其自身体型两倍的生物。 当一个生物的体型 A 和颜色 B 吸收了另一个同等大小的生物 C 和颜色 D (C \leq 2 \times A),它们将合并成一个大小相同的生物 A+C 和颜色 B。 在这里,根据两个生物的大小,它们有可能都可以吸收对方。
Snuke 一直在看着这些生物一遍又一遍地融合并最终成为一个生物。 找出该生物可能的颜色数量。
约束
- 2 \leq N \leq 100000
- 1 \leq A_i \leq 10^9
- A_i 是一个整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 … A_N
输出
输出最后一个生物的可能颜色数 N 生物反复合并并最终成为一个生物。
示例输入 1
3 3 1 4
示例输出 1
2
最后剩下的生物可能的颜色是颜色 1 和 3。 例如,当彩色生物 3 吸收彩色生物 2,然后是彩色生物 1 吸收彩色生物 3,最后剩下的生物的颜色将为 color 1.
示例输入 2
5 1 1 1 1 1
示例输出 2
5
可能有多个相同大小的生物。
示例输入 3
6 40 1 30 2 7 20
示例输出 3
4