Consider a histogram where $N$ rectangles with their bases parallel to the ground are attached consecutively. Each rectangle has a width of 1, and the height of the $i$-th rectangle from the left ($1 \le i \le N$) is an integer $H_i$.

The figure below shows an example of a possible histogram.

We want to find at most $K$ rectangles within this histogram such that their bases are parallel to the ground, their interiors do not overlap (excluding vertices and edges), each side has an integer length, and the sum of the areas of these rectangles is maximized. Let this value be $f(K)$.

Write a program that computes $f(1)$, $f(2)$, and $f(3)$.

Implementation Details

You must implement the following function:

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

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

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N \le 500\,000$
• $1 \le H_i \le 500\,000$ ($1 \le i \le N$)

Subtasks

1. (10 points)

   • $H_i \le H_{i+1}$ ($1 \le i \le N-1$)
   • If $|A| = 3$ and $f(1), f(2), f(3)$ are all correct, you receive 10 points.

2. (3 points)

   • $N \le 500$
   • If $|A| = 3$ and $f(1), f(2), f(3)$ are all correct, you receive 3 points.

3. (15 points)

   • $N \le 5\,000$
   • If $|A| = 2$ and $f(1), f(2)$ are both correct, you receive 3 points.
   • If $|A| = 3$ and $f(1), f(2), f(3)$ are all correct, you receive 15 points.

4. (27 points)

   • $N \le 200\,000$
   • If $|A| = 2$ and $f(1), f(2)$ are both correct, you receive 7 points.
   • If $|A| = 3$ and $f(1), f(2), f(3)$ are all correct, you receive 27 points.

5. (45 points)

   • No additional constraints.
   • If $|A| = 1$ and $f(1)$ is correct, you receive 1 point.
   • If $|A| = 2$ and $f(1), f(2)$ are both correct, you receive 15 points.
   • If $|A| = 3$ and $f(1), f(2), f(3)$ are all correct, you receive 45 points.

Note

Let $A$ be the array returned by the max_area function. If the size of $A$ is not between 1 and 3, you receive 0 points. Note that according to the subtask criteria, if any of the values $f(1), \dots, f(|A|)$ are incorrect, you receive 0 points. If all values $f(1), \dots, f(|A|)$ are correct, you can receive the points according to the scoring criteria of each subtask. In the criteria above, "$f(i)$ is correct" means that the size of $A$ is at least $i$ and the value of $A[i-1]$ is equal to $f(i)$. Note that the score for each subtask is the minimum of the scores for all data in that subtask.

Examples

Input 1

7
3 2 1 2 1 4 3

Output 1

7
11
13

Note 1

The three figures below show one of the cases where the sum of areas is maximized for $K=1, 2, 3$ respectively.

Note that if the max_area function returns [7, 11], you can receive points according to the subtask criteria because $f(1)$ and $f(2)$ are correct. Note that if the max_area function returns [7, 12, 13], you receive 0 points because $f(2)$ is incorrect even though $f(1)$ and $f(3)$ are correct. Note that if the max_area function returns [7, 11, 14], you receive 0 points because $f(3)$ is incorrect even though $f(1)$ and $f(2)$ are correct. This example satisfies the conditions for subtasks 2, 3, 4, and 5.

Input 2

7
1 2 3 4 5 6 7

Output 2

16
21
24

Note 2

This example satisfies the conditions for all subtasks.

Input 3

5
1 3 4 3 1

Output 3

9
11
12

Note 3

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

Interaction

The sample grader receives input in the following format:

• Line 1: $N$
• Line 2: $H_1 \ H_2 \ \dots \ H_N$

The sample grader outputs the following:

• Line $1 + i$ ($0 \le i < |A|$): The value of $A[i]$ for the array $A$ returned by the max_area function.

Note that the sample grader may differ from the grader used in actual evaluation.