题目内容

小华之前玩过一个游戏，在横轴上放了 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项面积最大为20。