最长不下降子序列

题目描述

给定 $n$ 个不超过 $10$ 的正整数 $a_i$, 对于每个位置 $i$ 的积分设置为：

位置 $i$ 之前的，以 $a_i$ 为结尾的最长不下降子序列的所有元素之和。
如果满足条件的序列有多个，则取位置字典序最小的那个子序列。例如：$\{1,3,2,4\}$, 以 $4$ 为结尾的最长不下降子序列有 $\{1,3,4\}$ 和 $\{1,2,4\}$, 其中 $3$ 对于 $2$ 的位置更靠前，所以取 $\{1,3,4\}$ 的和作为答案。

编写一个程序，输出每个位置的积分。

输入格式

第一行，$1$ 个数 $n$。
第二行，$n$ 个数，分别表示每个数字。

输出格式

一行，$n$ 个数，分别表示每个位置的积分。

样例 #1

样例输入 #1

5
1 2 5 3 4

样例输出 #1

1 3 8 6 10

样例 #2

样例输入 #2

4
2 3 1 5

样例输出 #2

2 5 1 10

样例 #3

样例输入 #3

5
1 7 5 9 6

样例输出 #3

1 8 6 17 12

提示

【样例解释 $1$】

五个位置的积分分别为 $(1),(1+2),(1+2+5),(1+2+3),(1+2+3+4)$

【样例解释 $2$】

四个位置的积分分别为 $(2),(2+3),(1),(2+3+5)$。

【样例解释 $3$】

五个位置的积分分别为 $(1),(1+7),(1+5),(1+7+9)$ ，$(1+5+6)$。

【数据规模】

对于 $50\%$ 的数据，$1\le n\le 500$；

对于 $80\%$ 的数据，$1\le n\le 10^3$；

对于 $100\%$ 的数据，$1\le n\le 10^4$。