Colorful Creatures

AtCoder

IDagc011_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3
3 1 4

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$.

Input #2

5
1 1 1 1 1

Output #2

5

There may be multiple creatures of the same size.

Input #3

6
40 1 30 2 7 20

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Colorful Creatures",
    "description": {
      "content": "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 anothe",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc011_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\nEvery creature can absorb anothe...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments