#P18834. [Croatian CPC2019] Herojski Histogram

[Croatian CPC2019] Herojski Histogram

[Croatian CPC2019] Herojski Histogram

题目描述

给定 nn 个正整数 h1,h2,…,hnh_1,h_2,\ldots,h_n。从原点开始,沿 xx 轴从左到右依次放置 nn 根柱子,第 jj 根柱子的宽为 11、高为 hjh_j,所有柱子的底边都在 xx 轴上,构成一个直方图。

下图分别对应两个样例中的直方图。

样例直方图

一个矩形可以放入直方图,当且仅当它的所有顶点坐标都是整数,各边均平行于坐标轴,且整个内部都被直方图覆盖。

对于每个 j=1,2,…,nj=1,2,\ldots,n,求只使用前 jj 根柱子组成的直方图中,能够放入的矩形的最大面积。

输入格式

第一行包含一个整数 nn(1≤n≤2×1051\le n\le2\times10^5)。

第二行包含 nn 个整数 h1,…,hnh_1,\ldots,h_n(1≤hi≤1071\le h_i\le10^7)。

输出格式

输出一行 nn 个整数,第 jj 个整数表示前 jj 根柱子组成的直方图中的最大矩形面积。

样例 1

输入

3
2 3 7

输出

2 4 7 

样例 2

输入

5
3 4 2 7 6

输出

3 6 6 8 12