配点 : $400$ 点

問題文

すぬけ君は，$N$ 匹の変わった生き物を見つけました． それぞれの生き物には色と大きさが定まっており，$i$ 番目の生き物の色は $i$，大きさは $A_i$ で表されます．

どの生き物も，大きさが自分の $2$ 倍以下であるような他の生き物を吸収することができます． 大きさ $A$，色 $B$ の生き物が大きさ $C$，色 $D$ の生き物を吸収すると ($C \leq 2 \times A$)，合体して大きさ $A+C$，色 $B$ の生き物になります． ここで，$2$ 匹の生き物の大きさによっては，どちらも他方を吸収することが可能な場合があります．

すぬけ君がこの生き物たちを観察していると，合体を繰り返して，最終的に $1$ 匹になりました． このとき，残った生き物の色として考えられるものは何種類あるかを求めてください．

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ … $A_N$

出力

この生き物たちが合体を繰り返して，最終的に $1$ 匹になったとき，残った生き物の色として考えられるものは何通りあるかを出力せよ．

3
3 1 4

2

最終的に残った生き物の色としては色 $1$, $3$ が考えられます． 例えば，色 $3$ の生き物が色 $2$ の生き物を吸収し，次に色 $1$ の生き物が色 $3$ の生き物と合体すると，色 $1$ の生き物のみが残ります．

5
1 1 1 1 1

5

同じ大きさの生き物が複数いる場合もあります．

6
40 1 30 2 7 20

4