Non‐Decreasing Subsequence Sum Score

Given a sequence of n digits (each between 0 and 9) held by n friends, for each friend you are to compute a score as follows: Consider all non‐decreasing subsequences (not necessarily contiguous) ending at that friend (i.e. using some of the digits up to and including that friend). Among all such subsequences, select the one with the longest length. If there are multiple with the same maximum length, choose the one that is lexicographically smallest (i.e. compare element by element; note that all subsequences end with the current digit). The score for the friend is defined as the sum of all digits in the chosen subsequence.

Note: A sequence a₁, a₂, …, a_k is non‐decreasing if \(a_{1}\le a_{2}\le \cdots \le a_{k}\). The lexicographical comparison is done by comparing the first differing element.

Example: For the input sequence [3, 2, 2, 2, 3], the scores are computed as follows:

• Friend 1 (3): Only sequence is [3] → score = 3.
• Friend 2 (2): Only sequence is [2] (since [3,2] is not non-decreasing) → score = 2.
• Friend 3 (2): The longest valid sequence is [2,2] (coming from Friend 2) → score = 4.
• Friend 4 (2): The longest valid sequence is [2,2,2] → score = 6.
• Friend 5 (3): The longest valid sequence is [2,2,2,3] → score = 9.

inputFormat

The first line contains an integer n indicating the number of friends. The second line contains n space-separated digits (each digit is between 0 and 9) representing the number each friend holds.

outputFormat

Output a single line containing n integers, where the i-th integer is the score computed for the i-th friend. The scores should be separated by a single space.

sample

5
1 2 3 4 5

1 3 6 10 15