# KOITST 22 Histogram

https://www.acmicpc.net/problem/25018

Let's consider a histogram where the base is parallel to the ground and consists of $N$ rectangles attached continuously on the ground. Each rectangle has a width of 1, and the height of the $i$th rectangle from the left, where $i$ ranges from 1 to $N$, is represented by the integer $H_i$.

Here's an illustration representing one possible histogram:

Within this histogram, we want to find up to $K$ rectangles with bases parallel to the ground, non-overlapping except at vertices and corners, and each side having an integer length. We aim to find these rectangles such that the sum of their areas is maximized. Let's denote this value as $f(K)$.

We need to write a program to compute $f(1)$, $f(2)$, and $f(3)$.

## Function List and Definitions:

You need to implement the following function:

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

* This function is called only once.
* The size of the integer array $H$ provided as an argument is $N$.
* Each element $H[i]$ in the array represents the height $H_{i+1}$ of the $(i+1)$th rectangle from the left $(0 \leq i \leq N - 1)$.
* This function should return an array $A$ with a size between 1 and 3. $A[i]$ should store $f(i+1)$ $(0 \leq i < |A|)$. Note that the grading criteria differ depending on the size of array $A$.

Constraints:

* $1 \leq N \leq 500,000$
* $1 \leq H_i \leq 500,000$ $(1 \leq i \leq N)$

## Subtasks:

Subtask 1 (10 points):
* If $H_i \leq H_{i+1}$ $(1 \leq i \leq N - 1)$, and all values of $f(1)$, $f(2)$, and $f(3)$ are correct, you get 10 points.

Subtask 2 (3 points):

* $N \leq 500$
* If all values of $f(1)$, $f(2)$, and $f(3)$ are correct, you get 3 points.

Subtask 3 (15 points):

* $N \leq 5,000$
* If $|A| = 2$ and both $f(1)$ and $f(2)$ are correct, you get 3 points.
* If $|A| = 3$ and all values of $f(1)$, $f(2)$, and $f(3)$ are correct, you get 15 points.

Subtask 4 (27 points):

* $N \leq 200,000$
* If $|A| = 2$ and both $f(1)$ and $f(2)$ are correct, you get 7 points.
* If $|A| = 3$ and all values of $f(1)$, $f(2)$, and $f(3)$ are correct, you get 27 points.

Subtask 5 (45 points):

No additional constraints.

### Scoring:

If the size of array $A$ is not between 1 and 3, you receive 0 points.
According to the criteria of each subtask, if any value of $f(i)$ is incorrect, you receive 0 points.
If all values of $f(1)$ through $f(|A|)$ are correct, you can receive points according to the scoring criteria of each subtask.

## Samples

Example 1:

Let's consider the case where $N = 7$ and $H = [3, 2, 1, 2, 1, 4, 3]$.

The grader calls the function:

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

There are three possible histograms shown in the figures for $K = 1, 2, 3$.


If the function returns [7, 11], it means $f(1)$ and $f(2)$ are correct, and you receive points according to the subtask criteria.

If the function returns [7, 12, 13], even if $f(1)$ and $f(3)$ are correct, $f(2)$ is incorrect, leading to 0 points.

If the function returns [7, 11, 14], even if $f(1)$ and $f(2)$ are correct, $f(3)$ is incorrect, leading to 0 points.

This example satisfies the conditions of subtasks 2, 3, 4, and 5.

Example 2:

Consider the case where $N = 7$ and $H = [1, 2, 3, 4, 5, 6, 7]$.

The grader calls the function:

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

In this case, all subtasks' conditions are satisfied.

Example 3:

Consider the case where $N = 5$ and $H = [1, 3, 4, 3, 1]$.

The grader calls the function:

This example satisfies the conditions of subtasks 2, 3, 4, and 5.

## Sample Grader:

The sample grader takes input in the following format:

* Line 1: $N$
* Line 2: $H_1$ $H_2$ ... $H_N$

The sample grader outputs:

* Line 1 + $i$ $(0 \leq i < |A|)$: The values of the array $A$ returned by the max_area function.

Note: The sample grader might differ from the actual grader used for scoring.