AT_abc163_e [ABC163E] Active Infants

[problemUrl]: https://atcoder.jp/contests/abc163/tasks/abc163_e $ N $ 人の幼児が左右一列に並んでおり、左から $ i $ 番目の幼児の活発度は $ A_i $ です。 あなたは一回だけ、幼児たちを好きな順番に並び替えさせることができます。 はじめ左から $ x $ 番目に並んでいた幼児が左から $ y $ 番目に移動するとき、うれしさが $ A_x\ \times\ |x-y| $ だけ生じます。 幼児のうれしさの合計が最大でいくつになるか求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2000 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力はすべて整数である。 ### Sample Explanation 1 左から $ 1 $ 番目の幼児を $ 3 $ 番目に、$ 2 $ 番目の幼児を $ 4 $ 番目に、$ 3 $ 番目の幼児を $ 1 $ 番目に、$ 4 $ 番目の幼児を $ 2 $ 番目に並ばせると、うれしさの合計は $ 1\ \times\ |1-3|+3\ \times\ |2-4|+4\ \times\ |3-1|+2\ \times\ |4-2|=20 $ になります。