def max_subarray_sum(arr):
    max_ending_here = max_so_far = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

def max_beauty_prefix(arr):
    n = len(arr)
    if n == 0:
        return []

    # Initialize DP arrays
    max_sum_no_swap = [0] * n
    max_sum_with_swap = [0] * n

    # Variables for tracking the sums
    current_max_no_swap = 0
    min_prefix_sum = 0
    prefix_sum = 0

    for i in range(n):
        # Update prefix sum
        prefix_sum += arr[i]

        # Kadane's algorithm step for max subarray sum without any swap
        current_max_no_swap = max(arr[i], current_max_no_swap + arr[i])
        max_sum_no_swap[i] = max(max_sum_no_swap[i - 1] if i > 0 else 0, current_max_no_swap)

        # Calculate max subarray sum with one swap
        if i == 0:
            max_sum_with_swap[i] = max_sum_no_swap[i]
        else:
            # Option 1: Use the no swap value
            max_sum_with_swap[i] = max_sum_no_swap[i]

            # Option 2: Swap the minimum prefix sum with current prefix sum
            max_sum_with_swap[i] = max(max_sum_with_swap[i], prefix_sum - min_prefix_sum)

            # Option 3: Swap the current element with a previous element
            for j in range(i):
                arr[j], arr[i] = arr[i], arr[j]
                new_max_subarray_sum = max_subarray_sum(arr[:i+1])
                max_sum_with_swap[i] = max(max_sum_with_swap[i], new_max_subarray_sum)
                arr[j], arr[i] = arr[i], arr[j]

        # Update min_prefix_sum
        min_prefix_sum = min(min_prefix_sum, prefix_sum)

    return max_sum_with_swap

import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
arr = list(map(int, data[1:n+1]))

# Calculate the beauty of each prefix
result = max_beauty_prefix(arr)

print(" ".join(map(str, result)))