题目描述

すぬけ君发现了 $N$ 只奇特的生物。每只生物都有确定的颜色和大小，第 $i$ 只生物的颜色为 $i$，大小为 $A_i$。

任意一只生物都可以吸收其它大小不超过自己两倍的生物。若大小为 $A$、颜色为 $B$ 的生物吸收了大小为 $C$、颜色为 $D$ 的生物（即 $C\leq 2\times A$），那么它们会合成一只大小为 $A+C$、颜色为 $B$ 的生物。在某些情况下，两只生物也可能互相满足吸收条件。

经过观察，すぬけ君发现这些生物进行多次合体后，最终只剩下一只生物。请你求出，最后剩下生物的颜色有多少种可能性。

输入格式

输入格式如下：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出在这些生物多次合体，最终只剩下一只生物时，最后剩下生物的颜色有多少种可能性。

样例 1

输入

3
3 1 4

输出

2

样例 2

输入

5
1 1 1 1 1

输出

5

样例 3

输入

6
40 1 30 2 7 20

输出

4

说明/提示

限制条件

• $2 \leq N \leq 100000$
• $1 \leq A_i \leq 10^9$
• $A_i$ 为整数

样例解释 1

作为最终剩下的生物颜色可能为颜色 $1$ 和 $3$。例如，颜色 $3$ 的生物可以先吸收颜色 $2$ 的生物，然后颜色 $1$ 的生物再和颜色 $3$ 的生物合体，最终只剩下颜色 $1$ 的生物。

样例解释 2

也有可能存在多个大小相同的生物。

由 ChatGPT 5 翻译