题目描述

有n根铁柱，依次笔直的摆放在1到n的坐标轴的位置上，第i根铁柱的长度为a[i],铁柱和坐标轴会围成一个不规则的多边形，例如有3根铁柱，长度依次为3,1,2,那么会和坐标轴形成如下图的多边形：形成多边形的面积为(3+1)*1/2+(1+2)*1/2=3.5

现在你可以进行任意次交换操作，每次操作可以交换相邻的铁柱，求形成多边形的最大面积s为多少？


输入格式

第一行一个整数n，表示有n根铁柱

接下来输入一行包含n个正整数a[1],a[2],...,a[n],分别表示n根铁柱的长度。

输出格式

输出最大围成的面积s,结果四舍五入保留两位小数

30%的数据保证:1<=n<=20

100%的数据保证：1<=n<=2e6,1<=a[i]<=2e6

输入/输出例子1

3
3 1 2

4.50

输入/输出例子2

2
5 5

5.00

输入/输出例子3

1
3

0.00