output_description: Print the maximum total happiness points the children can earn.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 ... A_N
attempt: import sys
  import numpy as np
  
  
  def f(n, a_):
      a = []
      for i, ai in enumerate(a_):
          a.append([1 + i, ai])
      a.sort(key=lambda x: x[1], reverse=True)
      dp = np.zeros(
          (n + 1, n + 1), np.int64
      )  # dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
      dp[1, 1] = a[0][1] * (n - a[0][0])
      dp[1, 0] = a[0][1] * (a[0][0] - 1)
      for i in range(2, n + 1):  # i人目の幼児。a[i-1]
          dp[i, 0] = dp[i - 1, 0] + a[i - 1][1] * abs(
              (a[i - 1][0] - 1 - (i - 1))
          )  # i人目を左にする。その時左に溜まっているのはi-1人
          dp[i, i] = dp[i - 1, i - 1] + a[i - 1][1] * abs(
              (n - a[i - 1][0] - (i - 1))
          )  # i人目を右にする。その時右に溜まっているのはi-1人
          # i人目を左に
          l = dp[i - 1, 1:i] + [
              a[i - 1][1] * abs((a[i - 1][0] - 1 - j)) for j in range(i - 2, -1, -1)
          ]  # j:左に溜まっている人数
          # i人目を右に
          r = dp[i - 1, : i - 1] + [
              a[i - 1][1] * abs((n - a[i - 1][0] - j)) for j in range(i - 1)
          ]  # j:右に溜まっている人数
          dp[i, 1:i] = np.maximum(l, r)
      return max(dp[n])
  
  
  if __name__ == "__main__":
      input = sys.stdin.readline
      n = int(input())
      a_ = list(map(int, input().split()))
      print(f(n, a_))
  
problem_description: Statement
  
  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.
samples: [{"input": "4\n    1 3 4 2", "output": "20\n    \n\nIf we move the 1-st child from the left to the 3-rd position from the left,\nthe 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and\nthe 4-th child to the 2-nd position, the children earns 1 \\times |1-3|+3\n\\times |2-4|+4 \\times |3-1|+2 \\times |4-2|=20 happiness points in total.\n\n* * *"}, {"input": "6\n    5 5 6 1 1 1", "output": "58\n    \n\n* * *"}, {"input": "6\n    8 6 9 1 2 1", "output": "85"}]