Maximum Subarray Sums for All Lengths

You are given an array of n integers. For each subarray length K from 1 to n, your task is to find the maximum sum of any contiguous subarray of that length.

Formally, let the array be \(a_1, a_2, \dots, a_n\). For each \(K\) (\(1 \le K \le n\)), you need to compute:

\(max_{1 \le i \le n-K+1} \sum_{j=i}^{i+K-1} a_j\)

Print the results for all \(K\) in a single line separated by spaces.

inputFormat

The first line contains a single integer n (the number of elements in the array). The second line contains n space-separated integers representing the array.

outputFormat

Output a single line containing n integers where the i-th integer is the maximum subarray sum of any contiguous subarray of length i (1-indexed).

## sample

5
1 2 3 4 5

5 9 12 14 15

</p>