小 A 的小店出售奥运纪念品，随着奥运会的临近，每天纪念品的价格都会上涨。
小 A 的展架上有 N 种不同的纪念品，编号分别是 1 \sim N，第 i 件纪念品在拿货回来第 1 天售卖的初始价格为 p_i，每过一天纪念品的售价会上涨，第 C 天的售价为 p_i \times C。
为了节约整理货架的时间，并能赚到更多的钱，小 A 制定了 2 条奇葩的规则。
每天只售卖 1 件纪念品，由于想要买的人太多了，因此每天他一定能成功的出售 1 件纪念品。
顾客只能选择被摆成一排的这些纪念品的第 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 卖完所有纪念品最多能赚到的钱。
5 3 5 2 8 4
75
3 \times 1 + 5 \times 2 + 2 \times 3 + 4 \times 4 + 8 \times 5 = 75