You are given a circular array balance of length n, where balance[i] is the net balance of person i.
In one move, a person can transfer exactly 1 unit of balance to either their left or right neighbor.
Return the minimum number of moves required so that every person has a non-negative balance. If it is impossible, return -1.
Note: You are guaranteed that at most 1 index has a negative balance initially.
Example 1:
Input: balance = [5,1,-4]
Output: 4
Explanation:
One optimal sequence of moves is:
i = 1 to i = 2, resulting in balance = [5, 0, -3]i = 0 to i = 2, resulting in balance = [4, 0, -2]i = 0 to i = 2, resulting in balance = [3, 0, -1]i = 0 to i = 2, resulting in balance = [2, 0, 0]Thus, the minimum number of moves required is 4.
Example 2:
Input: balance = [1,2,-5,2]
Output: 6
Explanation:
One optimal sequence of moves is:
i = 1 to i = 2, resulting in balance = [1, 1, -4, 2]i = 1 to i = 2, resulting in balance = [1, 0, -3, 2]i = 3 to i = 2, resulting in balance = [1, 0, -2, 1]i = 3 to i = 2, resulting in balance = [1, 0, -1, 0]i = 0 to i = 1, resulting in balance = [0, 1, -1, 0]i = 1 to i = 2, resulting in balance = [0, 0, 0, 0]Thus, the minimum number of moves required is 6.
Example 3:
Input: balance = [-3,2]
Output: -1
Explanation:
It is impossible to make all balances non-negative for balance = [-3, 2], so the answer is -1.
Constraints:
1 <= n == balance.length <= 105-109 <= balance[i] <= 109balance initially.