/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 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 匹になったとき，残った生き物の色として考えられるものは何通りあるかを出力せよ．
入力例 1
3 3 1 4
出力例 1
2
最終的に残った生き物の色としては色 1, 3 が考えられます． 例えば，色 3 の生き物が色 2 の生き物を吸収し，次に色 1 の生き物が色 3 の生き物と合体すると，色 1 の生き物のみが残ります．
入力例 2
5 1 1 1 1 1
出力例 2
5
同じ大きさの生き物が複数いる場合もあります．
入力例 3
6 40 1 30 2 7 20
出力例 3
4
Score : 400 points
Problem Statement
Snuke found N strange creatures. Each creature has a fixed color and size. The color and size of the i-th creature are represented by i and A_i, respectively.
Every creature can absorb another creature whose size is at most twice the size of itself. When a creature of size A and color B absorbs another creature of size C and color D (C \leq 2 \times A), they will merge into one creature of size A+C and color B. Here, depending on the sizes of two creatures, it is possible that both of them can absorb the other.
Snuke has been watching these creatures merge over and over and ultimately become one creature. Find the number of the possible colors of this creature.
Constraints
- 2 \leq N \leq 100000
- 1 \leq A_i \leq 10^9
- A_i is an integer.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 … A_N
Output
Print the number of the possible colors of the last remaining creature after the N creatures repeatedly merge and ultimately become one creature.
Sample Input 1
3 3 1 4
Sample Output 1
2
The possible colors of the last remaining creature are colors 1 and 3. For example, when the creature of color 3 absorbs the creature of color 2, then the creature of color 1 absorbs the creature of color 3, the color of the last remaining creature will be color 1.
Sample Input 2
5 1 1 1 1 1
Sample Output 2
5
There may be multiple creatures of the same size.
Sample Input 3
6 40 1 30 2 7 20
Sample Output 3
4