Reorder for Non-negative Prefix Sum

Given an array of integers, determine whether it is possible to reorder the array so that the sum of every prefix is non-negative. Formally, for a permutation \(p\) of \(\{1,2,\dots,n\}\), let the prefix sums be \(S_k = a_{p_1}+a_{p_2}+\cdots+a_{p_k}\) for \(1 \le k \le n\). The requirement is that \(S_k \ge 0\) for every valid \(k\).

For example, consider the array [1, 2, -3, 4, -2]. By reordering it as [4, 2, 1, -3, -2], the prefix sums become [4, 6, 7, 4, 2], each of which is non-negative. Hence, the answer is YES.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), the number of elements. The second line contains (n) integers (a_1, a_2, \dots, a_n) ((|a_i| \le 10^9)).

outputFormat

Print a single line with the answer: "YES" if it is possible to reorder the array so every prefix sum is non-negative, and "NO" otherwise.## sample

5
1 2 -3 4 -2

YES