Positive Prefixes :
Difficulty Level : Easy
Submissions : 154
Asked In :
Marks :10
: 0 | : 1
Prefix sum at position $$$i$$$ is defined as $$$prefix[i] = arr[0]+arr[1]+....arr[i]$$$
Rearrange the given array in such a way that no of the elements which are positive in the prefix sum array is maximum
Output the maximum number of positive elements possible in the prefix array after rearranging
Input
The first line contains $$$1 \le N \le 10^5$$$, denoting the number of elements in array $$$A$$$
The second line contains $$$N$$$ integers denoting elements of array $$$A$$$. $$$-10^9 \le A[i] \le 10^9 $$$
Output
Output a single integer denoting the maximum number of positive elements possible in rearranged $$$A$$$.
Examples
Input
4 -6 3 4 -10
Output
3
Input
4 -3 0 2 1
Output
3
