题目描述

酒随着时间的增加会愈发的醇香，这一天小可拿出了珍藏许久的 $n$ 瓶酒，每瓶酒都有一个初始价格 $a_i$，其中每瓶酒都按照 $1$ ～ $n$ 编号，这些酒放在了一个很长的盒子里，盒子两端是开口的，小可每天可以从盒子的两端取出一瓶选择卖出。

当一瓶酒在第 $x$ 天卖出时，会获得 $a_i \times x$ 的价值，小可想知道应该如何卖这些酒，可以使得其获得的价值最大。

输入格式

第一行一个正整数 $N$。

接下来 $2 \sim N+1$ 行，第 $i+1$ 行为一个正整数 $a_i$。

输出格式

一行一个整数表示答案。

样例

5
1
3
1
5
2

43

样例解释

样例解释 1

样例的最优解是：按 $1 \to 5 \to 2 \to 3 \to 4$ 的顺序卖酒，得到的钱数是 $1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 1 + 5 \times 5 = 43$。

数据范围

总共 $20$ 个测试点。

前 $2$ 个测试点 ，保证每种酒的初始价格都一样。

$3$ ～ $8$ 的测试点，$1 \le n \le 20$ 。

所有测试点， $1\le n \le 2000, 1 \le a_i \le 1000$