P2008 Big Friends' Numbers

At the NOIP2013 contest, Chang Shenniu slipped up badly and scored only $10$ points on the problem “Little Friends’ Numbers” (小朋友的数字): https://www.luogu.com.cn/problem/P1982. So, he decided to make fun of that problem.

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.

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

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

[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