There are $N$ children standing in a line from left to right. The activeness of the $i$-th child from the left is $A_i$. You can rearrange these children just one time in any order you like. When a child who originally occupies the $x$-th position from the left in the line moves to the $y$-th position from the left, that child earns $A_x\times |x-y|$ happiness points. Find the maximum total happiness points the children can earn.

Input is given from Standard Input in the following format: > $N$\ > $A_1 \quad A_2 \quad \cdots \quad A_N$ #### Constraints - $2\le N\le 2000$ - $1\le A_i\le 10^9$ - All values in input are integers.

Print the maximum total happiness points the children can earn.

***For Sample #1:*** If we move the $1$-st child from the left to the $3$-rd position from the left, the $2$-nd child to the $4$-th position, the $3$-rd child to the $1$-st position, and the $4$-th child to the $2$-nd position, the children earns $1\times |1-3|+3\times |2-4|+4\times |3-1|+2\times |4-2|=20$ happiness points in total.

AtCoder [ABC163E]