Maximum Visible Building Sums

Given a list of building heights, the task is to compute the maximum possible accumulated sum when selecting buildings in an optimal order to maximize the sum at each step. More formally, you are given an integer (n) and a list of (n) integers representing the heights of the buildings. By sorting the building heights in descending order, you then calculate the prefix sums. The (i)-th value of the result is the sum of the top (i) building heights. For example, if (n = 5) and the heights are ({3, 1, 4, 2, 5}), the sorted order is ({5, 4, 3, 2, 1}) and the prefix sums are ({5, 9, 12, 14, 15}).

inputFormat

Input is read from standard input (stdin) in the following format:

The first line contains a single integer (n) ((1 \le n \le 10^5)), representing the number of buildings. The second line contains (n) space-separated integers (h_1, h_2, \dots, h_n), where each (h_i) denotes the height of a building.

outputFormat

Output the prefix sums after sorting the heights in descending order. Print (n) space-separated integers on a single line to standard output (stdout).## sample

5
3 1 4 2 5

5 9 12 14 15