---

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）
  请在提交源代码前添加 #include "histogram.h"。

---

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「히스토그램」

我们来考虑一个由 $N$ 个底边平行于地面的矩形连续排列而成的直方图。每个矩形的宽度都是 $1$，并且从左到右第 $i$ $(1 \leq i \leq N)$ 个矩形的高度为整数 $H_{i}$。

下图展示了一个可能的直方图示例。

在这个直方图中，我们希望找到不超过 $K$ 个的矩形，这些矩形的底边平行于地面，且除了顶点和边之外的区域不重叠，并且每个边的长度都是整数，使得这些矩形的面积之和最大。这个值记为 $f(K)$。请编写一个程序来计算 $f(1), f(2), f(3)$。

---

实现细节

你需要实现以下函数：

vector<long long> max_area(vector<int> H);

• 该函数只会被调用一次。
• 参数中给定的整数数组 H 的大小为 $N$。数组的每个元素 H[i] $(0 \leq i \leq N-1)$ 表示从左到右第 $i+1$ 个矩形的高度 $H_{i+1}$。
• 该函数返回一个大小为 $1$ 到 $3$ 的数组 A。A[i] $(0 \leq i<|\texttt{A}|)$ 中应存储 $f(i+1)$ 的值。请注意，数组 A 的大小会影响评分标准。

注意，提交的代码中不应包含任何输入输出操作。

---

样例

样例 1

考虑 $N=7$, $H=[3,2,1,2,1,4,3]$ 的情况。

评测程序将调用如下函数：

max_area([3,2,1,2,1,4,3]) = [7,11,13]

下图展示了对于 $K=1,2,3$ 时面积之和最大的情况之一。

如果 max_area 函数返回 [7, 11]，则 $f(1)$ 和 $f(2)$ 都正确，可以根据子任务的评分标准得分。
如果 max_area 函数返回 [7, 12, 13]，则尽管 $f(1)$ 和 $f(3)$ 正确，但 $f(2)$ 错误，因此得 $0$ 分。
如果 max_area 函数返回 [7, 11, 14]，则尽管 $f(1)$ 和 $f(2)$ 正确，但 $f(3)$ 错误，因此得 $0$ 分。

这个样例满足子任务 $2,3,4,5$ 的条件。

样例 2

考虑 $N=7$, $H=[1, 2, 3, 4, 5, 6, 7]$ 的情况。

评测程序将调用如下函数：

max_area([1, 2, 3, 4, 5, 6, 7]) = [16, 21, 24]

这个样例满足所有子任务的条件。

样例 3

考虑 $N=5$, $H=[1,3,4,3,1]$ 的情况。

评测程序将调用如下函数：

max_area([1, 3, 4, 3, 1]) = [9, 11, 12]

这个样例满足子任务 $2,3,4,5$ 的条件。

---

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 5\cdot 10^5$
• $1 \leq H_{i} \leq 5\cdot 10^5$ $(1 \leq i \leq N)$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	10	$H_{i} \leq H_{i+1}$ $(1 \leq i \leq N-1)$
2	3	$N \leq 500$
3	15	$N \leq 5000$
4	27	$N \leq 2\cdot 10^5$
5	45	无附加限制

---

评分标准

在 LibreOJ 上，我们只会对 $f(1),f(2),f(3)$ 均正确的解决方案评分

假设 max_area 函数返回的数组为 A。

• 如果 A 的大小不是 $1$ 到 $3$ 之间，则得 $0$ 分。
• 根据子任务的标准，如果 $f(1), \cdots, f(|\texttt{A}|)$ 中有任何一个值不正确，则得 $0$ 分。
• 如果 $f(1), \cdots, f(|\texttt{A}|)$ 的值都正确，则根据子任务的评分标准得分。

在上述标准中，「$f(i)$ 正确」意味着 A 的大小至少为 $i$ 并且 A[i-1] 的值等于 $f(i)$。

每个子任务的分数是子任务所有数据的最小分数。

---

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2$ 行：$H_{1}\,H_{2}\,\cdots H_{N}$

示例评测程序按以下格式输出：

• 第 $1+i$ $(0 \leq i<|\texttt{A}|)$ 行：max_area 函数返回的数组 A 中 A[i] 的值

示例评测程序可能与实际评测程序不同。