Maximum Subarray Sum of Prefixes

You are given an array of integers. For each prefix of the array (i.e. the first k elements for k = 1, 2, ..., n), you need to compute the maximum subarray sum contained in that prefix. Formally, for each prefix of length k, compute:

[ \max_{1 \le i \le j \le k} \left( \sum_{t=i}^{j} a_t \right) ]

For example, consider the array [1, -2, 3, 4]:

• For k = 1, the only subarray is [1] and its sum is 1.
• For k = 2, possible subarrays are [1], [1,-2], [-2] with maximum sum 1.
• For k = 3, the best sum is 3.
• For k = 4, the best sum is obtained by the subarray [3,4] which gives 7.

Your task is to output the maximum subarray sum for each prefix, separated by spaces.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), the number of elements in the array. The second line contains n space-separated integers representing the array elements, which can be positive, negative, or zero.

outputFormat

Output a single line containing n space-separated integers. The i-th integer represents the maximum subarray sum in the prefix of length i.

4
1 -2 3 4

1 1 3 7