Two Posters

题意翻译

在某市的市中心有这么一块奇怪的广告牌。它由 $n$ 块垂直的面板组成，从左往右第 $i$ 块面板的宽度为 $1$，高度为**整数** $h_i$。一根水平的单杠连接着每块垂直面板的最顶部。你可以将每一块垂直面板上升任意**整数**高度，但必须要保证底部低于单杠或者正好在单杠上。 在操作完成之后，你将在这块广告牌上放两张矩形的海报。要求： - 一张海报必须完全在单杠上面，另一张必须完全在单杠下面。两张海报都不能够越过单杠。 - 两张海报都必须完全覆盖在广告牌内部。 如果你采取最优操作方案，求两张海报能够覆盖住的面积和的最大值。 数据范围： - $1\leqslant n\leqslant 10^4$。 - $1\leqslant h_i\leqslant 10^{12}$。 Translated by Eason_AC

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

6
2 2 3 5 4 5

输出样例 #1

18

输入样例 #2

1
1

输出样例 #2

1

说明

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.