CF1638F.Two Posters

You want to advertise your new business, so you are going to place two posters on a billboard in the city center. The billboard consists of $n$ vertical panels of width $1$ and varying integer heights, held together by a horizontal bar. The $i$-th of the $n$ panels has height $h_i$.

Initially, all panels hang down from the bar (their top edges lie on it), but before placing the two posters, you are allowed to move each panel up by any integer length, as long as it is still connected to the bar (its bottom edge lies below or on it).

After the moves are done, you will place two posters: one below the bar and one above it. They are not allowed to go over the bar and they must be positioned completely inside of the panels.

What is the maximum total area the two posters can cover together if you make the optimal moves? Note that you can also place a poster of $0$ area. This case is equivalent to placing a single poster.

你想为你的新业务做广告，因此你打算在市中心的广告牌上张贴两张海报。该广告牌由 $n$ 个宽度为 $1$、高度为不同整数的竖直面板组成，这些面板通过一根水平横杆连接固定。第 $i$ 个面板（共 $n$ 个）的高度为 $h_i$。

初始状态下，所有面板均从横杆向下垂挂（即其上边缘与横杆重合）；但在张贴两张海报之前，你可以将每个面板向上移动任意整数长度，只要它仍与横杆保持连接（即其下边缘位于横杆上或横杆下方）即可。

完成上述移动后，你将在横杆下方张贴一张海报，在横杆上方张贴另一张海报。海报不允许跨越横杆，且必须完全位于面板内部。

若你进行最优的面板移动，两张海报所能覆盖的最大总面积是多少？注意：你也可以张贴面积为 $0$ 的海报，这等价于仅张贴一张海报。

The first line of input contains one integer $n$ ($1 \le n \le 10^4$) — the number of vertical panels.

The second line of input contains $n$ integers $h_1, h_2, ..., h_n$ ($1 \le h_i \le 10^{12}$) — the heights of the $n$ vertical panels.

输入的第一行包含一个整数 $n$（$1 \le n \le 10^4$）—— 垂直面板的数量。

输入的第二行包含 $n$ 个整数 $h_1, h_2, ..., h_n$（$1 \le h_i \le 10^{12}$）—— $n$ 个垂直面板的高度。

Print a single integer — the maximum total area the two posters can cover together.

输出一个整数——两张海报共同覆盖的最大总面积。

In the first sample test, we can choose an upper poster with area $12$ and a lower poster of area $6$ as in the image below.

In the second sample test, we can cover the whole billboard using a single poster.

在第一个样例测试中，我们可以选择一张面积为 $12$ 的上部海报和一张面积为 $6$ 的下部海报，如下图所示。

在第二个样例测试中，我们可以使用一张海报覆盖整个广告牌。