Rearrange array to maximize positive prefix sums

Problem

You are given an integer array a of length n. You may rearrange the elements in any order.

Define the prefix sums of a permutation p as:

• pref[i] = p[0] + p[1] + ... + p[i] for 0 <= i < n

Let score(p) be the number of indices i such that pref[i] > 0.

Task

Compute the maximum possible value of score(p) over all permutations p of the array.

Input

• Integer array a (may contain negative, zero, and positive values).

Output

• An integer: the maximum number of positive prefix sums achievable.

Constraints

• 1 <= n <= 2 * 10^5
• -10^9 <= a[i] <= 10^9
• Target time complexity: O(n log n) (or better).

Example

• Input: [2, -1, 2, -3]
• One optimal permutation: [2, 2, -1, -3]
• Prefix sums: [2, 4, 3, 0] → positive prefix sums = 3 → Output: 3