CF1638F Two Posters

你想为你的新生意做广告，因此你打算在市中心的广告牌上张贴两张海报。广告牌由 $n$ 个宽度为 $1$、高度各不相同的竖直面板组成，这些面板通过一根水平横杆连接在一起。第 $i$ 块面板的高度为 $h_i$。  最初，所有面板都从横杆下方垂挂（它们的顶边与横杆重合），但在张贴两张海报之前，你可以将每块面板向上移动任意整数长度，只要它仍然与横杆连接（即其底边不高于横杆）。 移动完成后，你将张贴两张海报：一张在横杆下方，一张在横杆上方。海报不能越过横杆，且必须完全位于面板之内。 如果你采取最优的移动方式，这两张海报所能覆盖的最大总面积是多少？注意，你也可以选择张贴面积为 $0$ 的海报，这种情况等价于只张贴一张海报。

输入的第一行包含一个整数 $n$（$1 \le n \le 10^4$），表示竖直面板的数量。 第二行包含 $n$ 个整数 $h_1, h_2, ..., h_n$（$1 \le h_i \le 10^{12}$），表示 $n$ 块竖直面板的高度。

输出一个整数，表示两张海报所能覆盖的最大总面积。

在第一个样例中，我们可以选择一张面积为 $12$ 的上方海报和一张面积为 $6$ 的下方海报，如下图所示。  在第二个样例中，我们可以用一张海报覆盖整个广告牌。 由 ChatGPT 4.1 翻译