B - Minimum Number of Teams for Fundraising Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君の学校では文化祭の募金活動を行っており、 N 個のチームがそれぞれ募金を集めた。チーム i が集めた金額は A_i 円である。

学校の規定では、全チームの募金総額の半分以上を集めたチームの集まりを「表彰対象」とすることになっている。高橋君は、できるだけ少ないチーム数で表彰対象の条件を満たしたいと考えている。

具体的には、 N 個のチームからいくつかのチームを選び、選んだチームの募金額の合計が全チームの募金総額の半分以上（すなわち、総額を T としたとき \lceil T / 2 \rceil 以上）となるようにしたい。このような選び方のうち、選ぶチーム数が最小となるものを求め、その最小のチーム数を出力してください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である。

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、チームの数を表す整数 N が与えられる。
  • 2 行目には、各チームが集めた募金額を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

表彰対象の条件を満たすために必要な最小のチーム数を 1 行で出力してください。

入力例 1

5
10 20 30 40 50

出力例 1

2

入力例 2

4
5 5 5 5

出力例 2

2

入力例 3

12
8 15 3 22 7 14 30 6 11 25 9 18

出力例 3

4

入力例 4

30
120 45 300 75 210 90 15 480 60 135 255 195 30 405 150 225 345 105 270 390 165 510 240 315 435 180 360 285 555 600

出力例 4

9

入力例 5

1
1000000000

出力例 5

1

Score : 300 pts

Problem Statement

At Takahashi's school, a fundraising activity was held during the school festival, and N teams collected donations. Team i collected A_i yen.

According to the school regulations, a group of teams is eligible for an award if the sum of their donations is at least half of the total amount collected by all teams. Takahashi wants to satisfy this condition with as few teams as possible.

Specifically, he wants to select a subset of the N teams such that the sum of the donations of the selected teams is at least half of the total amount collected by all teams (i.e., at least \lceil T / 2 \rceil, where T is the total amount). Find the minimum number of teams that need to be selected, and print this minimum count.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of teams.
  • The second line contains N space-separated integers A_1, A_2, \ldots, A_N, representing the amount of donations collected by each team.

Output

Print the minimum number of teams required to satisfy the award condition in a single line.

Sample Input 1

5
10 20 30 40 50

Sample Output 1

2

Sample Input 2

4
5 5 5 5

Sample Output 2

2

Sample Input 3

12
8 15 3 22 7 14 30 6 11 25 9 18

Sample Output 3

4

Sample Input 4

30
120 45 300 75 210 90 15 480 60 135 255 195 30 405 150 225 345 105 270 390 165 510 240 315 435 180 360 285 555 600

Sample Output 4

9

Sample Input 5

1
1000000000

Sample Output 5

1