409231: GYM103463 K LTS buy wine

On a sunny afternoon, ltslts' friends came to visit him. So he decided to buy some wine.

All the wine in the store are known to be on the same shelf, these wine are numbered $$$1$$$ through $$$n$$$ from left to right.

ltslts' friends is very wealthy, so ltslts will buy all the wine. But his drinking capacity is limited, so he only buys a bottle of wine every day.

As we all konw, the longer the wine, the more valuable it is.

In the first, the $$$i$$$-th bottle of wine has a value $$$v_i$$$. On the $$$t$$$-th day, ltslts will buy a bottle of wine on the far left or right side of the shelf, and get the value $$$v_i \cdot t$$$.

Obviously, all the wine will be bought by ltslts on the $$$n$$$-th day, and he wants to know what the maximum value he could get.

For instance, we consider $$$n = 5$$$, and the value of wine are $$$\{1, 3, 1, 5, 2\}$$$.

• On the first day, we buy the wine on the far left and got $$$1$$$ value point, the remaining wine are $$$\{3, 1, 5, 2\}$$$.
• On the second day, we buy the wine on the far right and got $$$4$$$ value point, the remaining wine are $$$\{3, 1, 5\}$$$.
• On the third day, we buy the wine on the far left and got $$$9$$$ value point, the remaining wine are $$$\{1, 5\}$$$.
• On the fourth day, we buy the wine on the far left and got $$$4$$$ value point, the remaining wine are $$$\{5\}$$$.
• On the final day, we got $$$25$$$ value point, and we got a total of $$$43$$$ value point.

The first line contains a single integer $$$n(1 \leq n \leq 2000)$$$, denoting the number of wine.

In the next $$$n$$$ lines, each line contains a single integer $$$v_i(1 \leq v_i \leq 10^9)$$$ denoting the value of the $$$i$$$-th wine.

Print a single integer in one line: the maximum value ltslts could get.

5
1
3
1
5
2

43