$3s512MB$

Sample

题目描述

阪本先生有 $n$ 个矩形，这 $n$ 个矩形组成了一个直方图。具体来说，第 $i$ 个矩形的左下角、右下角、左上角、右上角坐标分别是 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$，其中 $h$ 是给定的长为 $n$ 得正整数序列。

现在你需要在这个直方图中找到不超过 $k$ 个矩形，满足：

• 每个矩形的每条边都和 $x$ 轴或 $y$ 轴平行。
• 这些矩形的内部面积互不重叠。这里边和角重叠是可行的。

你需要最大化这些矩形的面积之和。

设 $f(k)$ 为上述问题的答案，你需要求出 $f(1),f(2),f(3)$ 的值。

输入格式

输出一行三个正整数表示答案。

样例 1 输入

7
3 2 1 2 1 4 3

样例 1 输出

7 11 13

样例 1 解释

对于 $k=1$，选取的矩形左下角，右上角坐标分别为 $(0,0),(7,1)$。

对于 $k=2$，两个矩形的左下角，右上角坐标分别为 $\{(0,0),(5,1)\},\{(5,0),(7,3)\}$。

对于 $k=3$，三个矩形的左下角，右上角坐标分别为 $\{(0,0),(5,1)\},\{(0,1),(2,2)\},\{(5,0),(7,3)\}$。

样例 2-7

见选手目录下 $\rm sunset/ex\_sunset2.in\sim sunset/ex\_sunset7.in$ 和 $\rm sunset/ex\_sunset2.ans\sim sunset/ex\_sunset7.ans$

数据范围

对于所有数据，$1\le n\le 5\times 10^5,1\le h_i\le 10^9$。