Ježko Dušan a čajka Karolínka sú zlodeji. A špecializujú sa na banky. Karolínka vždy najskôr zvedie riaditeľa banky a po prehýrenej noci sa vytratí z jeho bytu aj s kľúčom od trezoru. Na ďalší deň Dušan nabehne zamaskovaný do banky a vďaka kľúču ju bleskovo vylúpi a rýchlo zmizne.
Bol dohodnutý s Karolínkou, že jej nechá jej podiel v smetnom koši na rohu Smrekovej a Bažinovej. Dušan je však ježko nepoctivý a rozhodol sa čajku ošidiť a dať jej menší podiel. Z banky ukradol $n$ mincí hodnôt $a_1$ až $a_n$ (niektoré môžu byť aj rovnaké). Teraz by si chcel zobrať väčší podiel. To znamená, že súčet hodnôt mincí, ktoré si zoberie Dušan musí byť väčší ako súčet mincí, ktoré dá Karolínke.
Aby však nebol príliš nápadný, chce si zobrať mincí čo najmenej. Zistite koľko najmenej mincí si Dušan musí zobrať, aby ich súčet bol väčší ako súčet zvyšných mincí.
Na vstupe dostanete hodnoty mincí, ktoré Dušan ukradol. Zistite, koľko najmenej mincí si musí zobrať, aby mal väčší podiel.
Na prvom riadku je číslo $n \, (1 \leq n \leq 1000)$ - počet ukradnutých mincí. Na druhom riadku sú hodnoty $a_1$ až $a_n \, (1 \leq ai \leq 1000)$.
Vypíšte jedno celé číslo – najmenší počet mincí, ktoré si Dušan musí zobrať, aby mal väčší podiel.
2
8 8
2
Dušan si musí zobrať obe mince. Ak by si zobral len jednu, podiel by bol rovnaký.
6
4 3 6 3 3 2
3
Ak si Dušan zoberie napríklad mince 6, 4 a 3 bude mať v súčte 12 peňazí, kým Karolínke zostane len 9.