AT_arc189_d [ARC189D] Takahashi is Slime

有 $N$ 个史莱姆排成一列，从左到右依次编号为 $1, 2, \ldots, N$。第 $i$ 个史莱姆的大小为 $A_i$。 对于每一个位置 $K = 1, 2, \ldots, N$，解决下面的问题： > 初始时，第 $K$ 个史莱姆是高桥君。高桥君可以执行任意多次（可以是 $0$ 次）的操作。请计算高桥君在操作后能达到的最大大小。 > > - 高桥君可以吸收一个相邻且大小小于他的史莱姆。吸收后，该史莱姆消失，高桥君的大小增加该史莱姆的大小。 > > 在这个过程中，被吸收的史莱姆消失后空出的位置会立即由两侧的史莱姆填补，这使得两端的史莱姆重新相邻（请参考样例 1）。

从标准输入读取以下格式的数据： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

对于每个 $K = 1, 2, \ldots, N$，输出问题的答案 $B_K$，各答案以空格分隔： > $B_1$ $B_2$ $\ldots$ $B_N$

- $2 \leq N \leq 5 \times 10^5$ - $1 \leq A_i \leq 10^9$ - 所有输入都是整数 ### 样例解释 以 $K = 4$ 为例。我们用方括号 `[]` 标识高桥君，称其为**列状态**。初始状态下的列为 $(4, 13, 2, [3], 2, 6)$。以下是高桥君的操作步骤： 1. 高桥君吸收右邻的史莱姆，大小变为 $3 + 2 = 5$，列状态变为 $(4, 13, 2, [5], 6)$。 2. 高桥君吸收左邻的史莱姆，大小变为 $5 + 2 = 7$，列状态变为 $(4, 13, [7], 6)$。 3. 高桥君吸收右邻的史莱姆，大小变为 $7 + 6 = 13$，列状态变为 $(4, 13, [13])$。 最终，高桥君再也无法吸收任何比他小的邻居，所以他的最大可能大小是 $13$。 **本翻译由 AI 自动生成**