分数: 700 点
问题陈述
有 N 史莱姆从左到右排成一排。
对于 i = 1, 2, \ldots, N, i左边第一个史莱姆有尺寸 A_i.
对于每个 K = 1, 2, \ldots, N,解决以下问题。
高桥是 K初始状态下从左边算起的第一个史莱姆。 求出在执行以下操作任意次数后他可以拥有的最大尺寸,可能为零:
- 选择一个与他相邻且严格小于他的史莱姆,并将其吸收。 结果,吸收的粘液消失,高桥的体型随着吸收的粘液的大小而增大。
当史莱姆因吸收而消失时,间隙立即闭合,并且与消失的史莱姆相邻的史莱姆(如果存在)变得相邻(参见示例输入 1 中的说明)。
约束
- 2 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案 B_K 对于每个 K = 1, 2, \ldots, N,以空格分隔,格式如下:
B_1 B_2 \ldots B_N
示例输入 1
6 4 13 2 3 2 6
示例输出 1
4 30 2 13 2 13
作为一个例子,考虑这个问题 K = 4。 我们将参考剩余史莱姆的尺寸,从左到右列出,其中高桥的尺寸括在方括号中 [ ],作为 行的状态。 也就是说,初始状态是 (4, 13, 2, [3], 2, 6)。考虑一下高桥的以下一系列行动。
- 他吸收了右边的粘液。结果,吸收的粘液消失了,他的尺寸变成了 3 + 2 = 5。状态变成 (4, 13, 2, [5], 6).
- 他吸收了左边的粘液。结果,吸收的粘液消失了,他的尺寸变成了 5 + 2 = 7。状态变成 (4, 13, [7], 6).
- 他吸收了右边的粘液。结果,吸收的粘液消失了,他的尺寸变成了 7 + 6 = 13。状态变成 (4, 13, [13]).
与他相邻的史莱姆没有严格小于他的,因此他无法执行任何更多动作。他的最终尺寸是 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