Remove 0 sum subarrays
Given
n integers, you are asked to remove all the contiguous subarrays that sum up to 0. You should start from the start of the array and move to the end of it, and as soon as a 0-sum-subarray is found, you should remove it from the array.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next line contains
n space-separated integers ( ≤ ≤ ).Output
The program should print the resulting array after removing all the subarrays that sum up to 0.
Examples
Input | Output |
8
5 -5 8 6 -14 9 9 -9 | 9 |
11
4 7 -11 8 7 10 -18 10 -17 20 25 | 20 25 |
Explanation
- Remove
[5, -5],[8, 6, -14], and[9, -9]
- Remove
[4 7 -11]and[8 7 10 -18 10 -17]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB