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: # -*- coding: utf-8 -*-
  
  import sys
  
  
  def input():
      return sys.stdin.readline().strip()
  
  
  def list2d(a, b, c):
      return [[c] * b for i in range(a)]
  
  
  def list3d(a, b, c, d):
      return [[[d] * c for j in range(b)] for i in range(a)]
  
  
  def list4d(a, b, c, d, e):
      return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
  
  
  def ceil(x, y=1):
      return int(-(-x // y))
  
  
  def INT():
      return int(input())
  
  
  def MAP():
      return map(int, input().split())
  
  
  def LIST(N=None):
      return list(MAP()) if N is None else [INT() for i in range(N)]
  
  
  def Yes():
      print("Yes")
  
  
  def No():
      print("No")
  
  
  def YES():
      print("YES")
  
  
  def NO():
      print("NO")
  
  
  sys.setrecursionlimit(10**9)
  INF = 10**18
  MOD = 10**9 + 7
  
  N = INT()
  A = LIST()
  
  A = [(a, i) for i, a in enumerate(A)]
  A.sort(reverse=1)
  
  # dp[i][j] := 左にi人、右にj人確定した状態での最大値
  dp = list2d(N + 1, N + 1, -INF)
  dp[0][0] = 0
  for i, (a, x) in enumerate(A):
      # j := 今左に確定してる人数
      for j in range(i + 1):
          # k := 今右に確定してる人数
          k = i - j
          # このaを左にする遷移
          y = j
          dp[j + 1][k] = max(dp[j + 1][k], dp[j][k] + abs(x - y) * a)
          # このaを右にする遷移
          y = N - 1 - k
          dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + abs(x - y) * a)
  ans = 0
  for i in range(N + 1):
      # 左右に計N人決まった状態での最大を取る
      ans = max(ans, dp[i][N - i])
  print(ans)
  
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"}]