Sort by Group Sum
You are given a list of N integers. The integers are grouped such that consecutive identical integers belong to the same group. For example, [1, 1, 2, 3, 3, 3, 1] has groups [1, 1], [2], [3, 3, 3], and [1]. Your task is to sort these groups based on the sum of the elements within each group in ascending order. If two groups have the same sum, the group that appeared earlier in the original list should come first (stable sort). Print the elements of the sorted groups in their original order.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print N space-separated integers, representing the elements of the groups sorted as described.
Constraints
1 <= N <= 200000. Each integer is between -10^9 and 10^9.
Example 1
7 1 1 2 3 3 3 1
1 1 1 2 3 3 3
Groups are [1,1] (sum 2, index 0), [2] (sum 2, index 2), [3,3,3] (sum 9, index 3), [1] (sum 1, index 6). Sorted by sum then index: [1] (sum 1), [1,1] (sum 2, index 0), [2] (sum 2, index 2), [3,3,3] (sum 9). Output: 1 1 1 2 3 3 3
Example 2
5 -1 -1 5 2 2
-1 -1 2 2 5
Groups are [-1,-1] (sum -2, index 0), [5] (sum 5, index 2), [2,2] (sum 4, index 3). Sorted: [-1,-1] (sum -2), [2,2] (sum 4), [5] (sum 5). Output: -1 -1 2 2 5
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
7 1 1 2 3 3 3 1
5 -1 -1 5 2 2