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()))
  right = 0
  left = n - 1
  stay = []
  l = []
  ans = 0
  for i in range(n):
      l.append([a[i], i])
  l.sort(reverse=True)
  for i in range(n):
      l0 = 0
      r0 = 0
      for j in range(l[i][1] - 1):
          r0 = max(r0, a[j])
      for j in range(l[i][1] + 1, n):
          l0 = max(l0, a[j])
      r0 = l[i][0] - r0
      l0 = l[i][0] - l0
      # print(l0,r0)
      if len(stay) == 0:
          if (left - l[i][1]) * r0 > (l[i][1] - right) * l0:
              ans += l[i][0] * (left - l[i][1])
              left -= 1
          elif (left - l[i][1]) * r0 < (l[i][1] - right) * l0:
              ans += l[i][0] * (l[i][1] - right)
              right += 1
          else:
              stay.append(l[i])
          a[l[i][1]] = 0
      else:
          k = len(stay)
          if (left - l[i][1] - k // 2) * r0 > (l[i][1] - right - k // 2) * l0:
              for j in range(k):
                  if j % 2 == 0:
                      ans += (stay[k - 1 - j][1] - right - k // 2 + j) * stay[k - 1 - j][
                          0
                      ]
                      right += 1
                  else:
                      ans += (left - stay[k - 1 - j][1] - k // 2 + j) * stay[k - 1 - j][0]
                      left -= 1
              ans += l[i][0] * (left - l[i][1])
              left -= 1
              stay = []
          elif (left - l[i][1] - k // 2) * r0 < (l[i][1] - right - k // 2) * l0:
              for j in range(k):
                  if j % 2 == 1:
                      ans += abs(
                          (stay[k - 1 - j][1] - right - k // 2 + j) * stay[k - 1 - j][0]
                      )
                      right += 1
                  else:
                      ans += abs(
                          (left - stay[k - 1 - j][1] - k // 2 + j) * stay[k - 1 - j][0]
                      )
                      left -= 1
              ans += l[i][0] * (l[i][1] - right)
              right += 1
              stay = []
          else:
              stay.append(l[i])
          a[l[i][1]] = 0
      # print(stay,ans)
  if len(stay) > 0:
      k = len(stay)
      for j in range(k):
          if j % 2 == 0:
              ans += abs((stay[k - 1 - j][1] - right - k // 2 + j) * stay[k - 1 - j][0])
              right += 1
          else:
              ans += abs((left - stay[k - 1 - j][1] - k // 2 + j) * stay[k - 1 - j][0])
              left -= 1
  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"}]