← 返回 amazon 的题目列表Arrange Array for Maximum Index of Non-Positive Prefix Sum
类型：online_judge
Given an integer array importance of length n, where each element is between [-10^9, 10^9]. You can rearrange the order of elements to ensure that no prefix sum is non-positive. If it's not possible, output -1. If possible, construct a permutation such that the index of the first non-positive prefix sum is maximized.
Input:
Integer n (1 <= n <= 10^5)
Integer array importance
Output:
Output -1 if it's not possible to have all positive prefix sums
Otherwise, output the maximum index of the first non-positive prefix sum.
Example 1:
Input: 2 [1, 2]
Output: -1
Example 2:
Input: 4 [1, 2, -6, 3]
Output: 3 (A possible arrangement is [3, 2, 1, -6])
Example
Input
2
1 2