Sanky has got K (1 <= K <= 1500) items and wants to sell them. He sells one item per day and intends to maximize the profit over a period of time.

Items have some characteristic features:
• Numbering of items are done from 1 to K and kept sequentially in a container which is open at both ends. On any day, Sanky can retrieve one item from either end of his box of items.
• Durability of items improve with time and thereby increasing their price.
• The items are not uniform: some are better and have higher value. Item x has value v(x) (1 <= v(x) <= 500).
• Buyer pay more for items that have higher durability: a buyer will pay v(x)*d for item of durability d.

Given the values v(x) of each of the items kept in order of the index x in the container, what is the maximum value Sanky can receive if he orders the sale of the items optimally?

The first item sold on day 1 has durability d=1. Each subsequent day durability increases by 1.

Input

The first line consists of the number of items, K.

Next K lines contains a single integer per line giving the value of item v(x).

Input is terminated by End Of File.

There will be maximum 25 test cases.

Output

The maximum profit Sanky can receive by selling the items.

Sample Input

``` 5 2 7 9 8 3 ```

Sample Output

``` 106 ```

Problem Setter: Nitish Agarwal

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0