#P18834. [Croatian CPC2019] Herojski Histogram
[Croatian CPC2019] Herojski Histogram
[Croatian CPC2019] Herojski Histogram
题目描述
给定 个正整数 。从原点开始,沿 轴从左到右依次放置 根柱子,第 根柱子的宽为 、高为 ,所有柱子的底边都在 轴上,构成一个直方图。
下图分别对应两个样例中的直方图。

一个矩形可以放入直方图,当且仅当它的所有顶点坐标都是整数,各边均平行于坐标轴,且整个内部都被直方图覆盖。
对于每个 ,求只使用前 根柱子组成的直方图中,能够放入的矩形的最大面积。
输入格式
第一行包含一个整数 ()。
第二行包含 个整数 ()。
输出格式
输出一行 个整数,第 个整数表示前 根柱子组成的直方图中的最大矩形面积。
样例 1
输入
3
2 3 7
输出
2 4 7
样例 2
输入
5
3 4 2 7 6
输出
3 6 6 8 12