您想要宣传您的新业务,因此您将在市中心的广告牌上放置两张海报。广告牌由 $$$n$$$ 宽度为 $$$1$$$ 和不同整数高度的垂直面板组成,由水平条固定在一起。 $$$n$$$ 面板中的第 $$$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$$$ 垂直面板的高度。
输出
打印一个整数 - 两张海报可以一起覆盖的最大总面积。
示例
输入 #1
6 2 2 3 5 4 5
输出 #1
18
输入 #2
1 1
输出 #2
1
注意
在第一个样本测试中,我们可以选择面积为$$$12$$$的上部海报和面积为$$$6$$$的下部海报,如下图所示。
在第二个示例测试中,我们可以使用一张海报覆盖整个广告牌。