题目描述

小 $A$ 的小店出售奥运纪念品，随着奥运会的临近，每天纪念品的价格都会上涨。

小 $A$ 的展架上有 $N$ 种不同的纪念品，编号分别是 $1 \sim N$，第 $i$ 件纪念品在拿货回来第 $1$ 天售卖的初始价格为 $p_i$，每过一天纪念品的售价会上涨，第 $C$ 天的售价为 $p_i \times C$。

为了节约整理货架的时间，并能赚到更多的钱，小 $A$ 制定了 $2$ 条奇葩的规则。

1. 每天只售卖 $1$ 件纪念品，由于想要买的人太多了，因此每天他一定能成功的出售 $1$ 件纪念品。

2. 顾客只能选择被摆成一排的这些纪念品的第 $1$ 个或者最后一个。

请问 $N$ 天之后，当小 $A$ 的纪念品全部卖完，小 $A$ 最多能收到多少钱？

输入格式

第 $1$ 行读入整数 $N$。（$1 \le N \le 2000$）

接下来 $N$ 行，每行读入 $1$ 个整数，第 $i$ 个整数 $p_i$ 代表的是第 $i$ 件纪念品的在拿货回来第 $1$ 天售卖的初始价格。（$1 \le p_i \le 1000$）

输出格式

输出小 $A$ 卖完所有纪念品最多能赚到的钱。

样例输入 #1

5
3
5
2
8
4

样例输出 #1

75