高桥是史莱姆

时间限制：5s
空间限制：1024MB

题目描述

有 $N$ 个史莱姆从左到右排成一列，第 $i$ 个史莱姆的大小为 $A_i$。对每个起点 $K=1,2,\ldots,N$，初始时第 $K$ 个史莱姆是高桥。高桥可以执行任意多次以下操作：吸收一个与他相邻且大小严格小于他的史莱姆，被吸收的史莱姆消失，高桥的大小增加该史莱姆原来的大小；空位会立即合拢，使两侧仍存活的史莱姆重新相邻。

请分别求出每个起点 $K$ 下高桥最终可能达到的最大大小。

输入格式

第一行一个整数 $N$，第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出 $N$ 个整数，第 $K$ 个整数表示从位置 $K$ 开始时的答案。

样例输入 1

6
4 13 2 3 2 6

样例输出 1

4 30 2 13 2 13

样例输入 2

12
22 25 61 10 21 37 2 14 5 8 6 24

样例输出 2

22 47 235 10 31 235 2 235 5 235 6 235

数据范围

• $2\le N\le 5\times 10^5$；
• $1\le A_i\le 10^9$；
• 输入均为整数。