D. Da Hong Pao
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Evgeny doesn't like to work at all, but he really enjoys Da Hong Pao tea, which is known for its relaxing effect. During a tea session with Da Hong Pao, Evgeny wondered how he could maximize his total relaxation.

During the session, he is offered $$$n$$$ cups of different types of his favorite tea, each with its own relaxation coefficient $$$a_i$$$. The tea cups are arranged in a row, without gaps, equidistant from each other. To maintain the aesthetics that Evgeny values very much, he acts as follows: while there are still some cups left on the table, pick either the leftmost or the rightmost remaining cup, and drink all tea from that cup. After that, the server removes the cup from the table.

From the first cup he drinks during the session, Evgeny gets $$$x_1$$$ units of relaxation, where $$$x_1$$$ is the relaxation coefficient for the first cup of tea he drinks. From the next cup, he gets $$$2 x_2$$$ units of relaxation, where $$$x_2$$$ is the relaxation coefficient for the second cup of tea he drinks. And so on: from the $$$i$$$-th cup he drinks, Evgeny gets $$$i x_i$$$ units of relaxation.

Help Evgeny determine the maximum total amount of relaxation he can achieve during the Da Hong Pao session.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 5000$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$): the relaxation coefficients of all the Da Hong Pao cups provided to Evgeny.

Output

Output a single integer: the maximum total relaxation value that Evgeny can achieve during the Da Hong Pao session.

Examples
Input
4
1 2 3 4
Output
30
Input
4
1 2 1 1
Output
14