{"raw_statement":[{"iden":"problem statement","content":"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$.\nYou can rearrange these children just one time in any order you like.\nWhen 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.\nFind the maximum total happiness points the children can earn."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2000$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $...$ $A_N$"},{"iden":"sample input 1","content":"4\n1 3 4 2"},{"iden":"sample output 1","content":"20\n\nIf 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."},{"iden":"sample input 2","content":"6\n5 5 6 1 1 1"},{"iden":"sample output 2","content":"58"},{"iden":"sample input 3","content":"6\n8 6 9 1 2 1"},{"iden":"sample output 3","content":"85"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}