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: n = int(input())
  a = list(map(int, input().split()))
  from collections import Counter
  
  dp = [[0 for _ in range(n + 1)] for _ in range(n)]
  cnt = Counter()
  dic = {}
  for i in range(n):
      if dic.get(a[i]) is None:
          dic[a[i]] = [i]
      else:
          dic[a[i]] += [i]
      cnt[a[i]] += 1
  
  
  def maximize(rang, pos):
      lb_rang = 0
      ub_rang = len(rang) - 1
      lb_pos = 0
      ub_pos = len(pos) - 1
      ret = 0
      while lb_rang <= ub_rang:
          if abs(rang[lb_rang] - pos[ub_pos]) < abs(rang[ub_rang] - pos[lb_pos]):
              ret += abs(rang[ub_rang] - pos[lb_pos])
              ub_rang -= 1
              lb_pos += 1
          else:
              ret += abs(rang[lb_rang] - pos[ub_pos])
              lb_rang += 1
              ub_pos -= 1
      return ret
  
  
  sorted_keys = sorted(cnt.keys())
  acm = 0
  for x in sorted_keys:
      num = cnt[x]
      for i in range(n):
          if i + acm + num <= n:
              if acm == 0:
                  dp[i][acm + num] = x * maximize(list(range(i, i + num)), dic[x])
              else:
                  for j in range(i, i + num + 1):
                      # print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                      # print(j,acm,dp[j][acm])
                      dp[i][acm + num] = max(
                          dp[i][acm + num],
                          dp[j][acm]
                          + x
                          * maximize(
                              list(range(i, j)) + list(range(j + acm, i + acm + num)),
                              dic[x],
                          ),
                      )
      acm += num
  
  print(max(dp[0]))
  
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"}]