Problem Background

At the NOIP2013 competition, Chang, the legendary cow, spectacularly messed up and only scored 10 points on the problem about the little friends' numbers. Therefore, he decided to tweak the problem a bit.

Problem Description

There is a group of big friends (aged 15 years or older), each holding a single-digit number, which is between 0 and 9. Each big friend's score is the sum of all numbers in the longest non-decreasing subsequence that ends with their number. If there are multiple such longest subsequences, the one with the smallest lexicographical order of indices is chosen. Given the number \( n \) of big friends and their respective numbers, you are asked to calculate the score for each of them.

Input Format

The first line contains a single number \( n \).

The second line contains \( n \) numbers, representing the numbers each big friend is holding.

Output Format

A single line containing \( n \) numbers, representing the scores of each big friend.

Sample Input and Output

Sample Input #1

5
1 2 5 3 4

Sample Output #1

1 3 8 6 10

Sample Input #2

5
1 7 5 9 6

Sample Output #2

1 8 6 17 12

Notes

Sample Explanation 1

The scores for the five friends are \((1)\), \((1+2)\), \((1+2+5)\), \((1+2+3)\), \((1+2+3+4)\).

Sample Explanation 2

The scores for the five friends are \((1)\), \((1+7)\), \((1+5)\), \((1+7+9)\) (also \((1,5,9)\)), \((1+5+6)\).

Data Scale

For 50% of the data, \(1 \le n \le 500\);

For 80% of the data, \(1 \le n \le 10^3\);

For 100% of the data, \(1 \le n \le 10^4\).

见题面 Input 部分

见题面 Output 部分