# Sell the Items

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