Description

There is a group of “big friends” (age $15$ or above). Each of them holds a number, which has exactly $1$ digit, i.e., it is between $0$ and $9$. The score of each big friend is defined as the sum of all numbers in the longest non-decreasing subsequence that appears before them and ends at them. (This sequence must end at that person!) If there are multiple longest non-decreasing subsequences, choose the one whose sequence of indices is lexicographically smallest. Now you are given $n$ big friends and their numbers. Please compute the score of each person.

Input Format

The first line contains $1$ number $n$.

The second line contains $n$ numbers, representing each person’s number.

Output Format

Output $n$ numbers in one line, representing each person’s score.

5
1 2 5 3 4

1 3 8 6 10

5
1 7 5 9 6

1 8 6 17 12

Hint

[Sample Explanation $1$]

The five scores are $(1)$, $(1+2)$, $(1+2+5)$, $(1+2+3)$, $(1+2+3+4)$.

[Sample Explanation $2$]

The five scores are $(1)$, $(1+7)$, $(1+5)$, $(1+7+9)$ (there is also $(1,5,9)$), $(1+5+6)$.

Constraints

For $50\%$ of the testdata, $1 \le n \le 500$.

For $80\%$ of the testdata, $1 \le n \le 10^3$.

For $100\%$ of the testdata, $1 \le n \le 10^4$.

Translated by ChatGPT 5