题目描述

有一排小朋友，每人手上拿着一个 $0$ 到 $9$ 之间的数字。每位小朋友的得分定义为：以他为结尾的最长不下降子序列中所有数字之和。（子序列必须以他作为最后一个元素！）如果存在多个最长不下降子序列，则选择下标字典序最小的那个。

现已知有 $n$ 个小朋友以及他们各自的数字，请你求出每位小朋友的得分。

输入格式

第一行，$1$ 个整数 $n$。

第二行，$n$ 个整数，分别表示每位小朋友的数字。

输出格式

一行，$n$ 个整数，分别表示每位小朋友的得分。

样例

5
1 2 5 3 4

1 3 8 6 10

5
1 7 5 9 6

1 8 6 17 12

提示

【样例解释 $1$】

五位小朋友的得分分别为 $(1),(1+2),(1+2+5),(1+2+3),(1+2+3+4)$。

【样例解释 $2$】

五位小朋友的得分分别为 $(1),(1+7),(1+5),(1+7+9)$（另一个 $(1,5,9)$ 长度相同但下标字典序更大），$(1+5+6)$。

【数据规模】

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

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

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