题解

题目描述

在横轴上有 $n$ 个宽度均为 1 的相邻矩形，第 $i$ 个矩形的高度为 $h_i$，它们共同构成了一个直方图。普通的「最大矩形面积」问题是：在不改变顺序的前提下，找到可以完全覆盖在直方图之下的、面积最大的矩形。

本题在此基础上允许你 执行一次任意两根柱子高度的交换，问：在进行至多一次交换之后，能得到的最大矩形面积是多少？

题目内容

小华之前玩过一个游戏，在横轴上放了$n$ 个相邻的矩形，每个矩形的宽度是 $1$ ，而第 $i(1≦i≦n)$ 个矩形的高度为 $h_i$，这 $n$ 个矩形构成了一个直方图，在直方图中找出能够勾勒出来的矩形的最大面积。

这个游戏小华已经玩得很腻了，于是小华就想增加一下难度，现在有 $1$ 次交换任意 $2$ 个矩形的操作，请问在交换后，能够勾勒出的最大的短形面积能达到多少呢?

输入描述

第一行包含一个整数 $n(2≦n≦10^5)$，表示矩形个数。

第二行包含 $n$ 个整数，依次为 $h_1,h_2,..., h_n(1 ≦ h_i≦ 10^4)$ ，表示矩形的高度。

输出描述

输出一个整数，表示在交换后能够勾勒出的最大的矩形面积。

样例1

输入

6
3 1 6 5 2 3

输出

12

说明

交换第 $2$ 个与第 $6$ 个元素，数组变为 $[3,3,6,5,2,1]$ ，此时前 $4$ 项面积最大为 $12$ 。

样例2

输入

7
5 5 3 5 5 2 4

输出

20

说明

交换第 $3$ 个与第 $7$ 个元素，数组变为 $[5,5,4,5,5,2,3]$ ，此时前 $5$ 项面积最大为 $2 0$ 。