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.

-----Constraints-----
 - 2 \leq N \leq 2000
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the maximum total happiness points the children can earn.

-----Sample Input-----
4
1 3 4 2

-----Sample Output-----
20

If we move the 1-st child from the left to the 3-rd position from the left, the 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and the 4-th child to the 2-nd position, the children earns 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 happiness points in total.

Difficulty: interview

Starter code:

Solutions:
N = int(input())
A = [int(s) for s in input().split(" ")]
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a,i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    
  prev = curr
 
print(max(prev))

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

    dp = [[0] * (N + 1) for _ in range(N + 1)]

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print((max(dp[N])))

def __starting_point():
    N = int(input())
    A = list(map(int, input().split()))
    solve(N, A)

__starting_point()

# E - Active Infants
N = int(input())
A = list(map(int,input().split()))
dp = [[] for _ in range(N+1)]
dp[0].append(0)
for i in range(N):
    A[i] = [A[i],i+1]
A.sort(reverse=True)
for M in range(1,N+1):
    Ai,i = A[M-1]
    # x=0
    dp[M].append(dp[M-1][0]+Ai*(N-(M-1)-i))
    # 1<=x<=M-1
    for x in range(1,M):
        dp[M].append(max(dp[M-1][x-1]+Ai*(i-x),dp[M-1][x]+Ai*(N-(M-x-1)-i)))
    # x=M
    dp[M].append(dp[M-1][M-1]+Ai*(i-M))
print(max(dp[N]))

from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    a = [(int(v), i) for i, v in enumerate(input().split())]
    a.sort(reverse=True)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = a[0][0] * (n - 1 - a[0][1])
    dp[0][1] = a[0][0] * a[0][1]
    for i, v in enumerate(a[1:]):
        dp[i+1][0] = dp[i][0] + v[0] * abs(n - 1 - (i + 1) - v[1])
        dp[i+1][i+2] = dp[i][i+1] + v[0] * abs(v[1] - (i + 1))
        for j in range(1, i + 2):
            dp[i+1][j] = max(
                dp[i][j] + v[0] * abs(n - 1 - (i + 1) + j - v[1]),
                dp[i][j-1] + v[0] * abs(v[1] - (j - 1)))
    ans = -float('inf')
    for i in dp[n-1]:
        ans = max(ans, i)
    print(ans)


main()

def main():  
  import sys
  input = sys.stdin.readline
  n = int(input())
  a = [int(i) for i in input().split()]
  b = [int(i) for i in range(n)]
  ab = [(x,y) for x,y in zip(a,b)]
  from operator import itemgetter
  ab = sorted(ab,key=itemgetter(0),reverse=True)
  dp = [[-10**14]*(n+1) for i in range(n+1)]
  dp[0][0] = 0
  for i in range(n):
    for j in range(i+2):
      if j >= 1:
        dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
      if j == 0:
        dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
  print(max(dp[n]))
def __starting_point():
    main()
__starting_point()

'''
着想：大きいaほど左右の端に移動したい、小さいaを先に端にやるより必ず大きくなるから
問題：単純に貪欲に大きいaから左端(x-1)と右端(N-x)の大きい方に移動すると、
      残りのaの組み合わせ的に最適でない場合がある
      アイテムの左右端の単純な割り振りはO(2^N)
解決策の着想：大きい順のk個を(k=L+R)となる
    　　左L個右R個にどのように割り振っても(k+1)個目の最適な割り振り方は変わらない
解決策：アイテムk個左右に割り振る状態をdp[L][R]で保存O(N^2)
'''

def solve():
  N = int(input())
  A = [[a, i] for a,i in zip(map(int, input().split()), range(N))]
  A.sort(key=lambda a: a[0], reverse=True)

  dp = [[0]*(N+1) for _ in range(N+1)] # 左からxマス右からyマス埋める
  for i in range(0,N):
    a, l = A[i]
    for x in range(0,i+1):
      y = i - x # 合計x+y=iマス既に埋まっている、次にi+1マス目を考える
      dp[x+1][y] = max(dp[x+1][y], dp[x][y] + a * abs(l - x))
      dp[x][y+1] = max(dp[x][y+1], dp[x][y] + a * abs(l - (N-y-1)))

  print(max(dp[N-i][i] for i in range(N+1)))
  
solve()

def main():
    n = int(input())
    tmp = list(map(int, input().split()))
    a = [[v, i] for i, v in enumerate(tmp)]
    a.sort(reverse=True)
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n):
        v, idx = a[i]
        for j in range(i+1):
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+v*abs(idx-j))
            dp[i+1][j] = max(dp[i+1][j] , dp[i][j]+v*abs(idx - (n-1-i+j)))
    print(max(dp[n]))

def __starting_point():
    main()
__starting_point()

n = int(input())
a = list(map(int, input().split()))

a = list(enumerate(a))
a.sort(key=lambda x: x[1])

# dp[left + right][left]
dp = [[] for _ in range(n+1)]
dp[0].append(0)

for i in range(1, n+1): # i = left + right
    ind, act = a.pop(-1)

    # all right
    dp[i].append(dp[i-1][0] + act * (n - i - ind))

    # middle
    for j in range(1, i): # j = left
        ar = dp[i-1][j] + act * (n - i + j - ind) # rightに追加
        al = dp[i-1][j-1] + act * (ind - j + 1) # leftに追加
        dp[i].append(max([ar, al]))

    # all left
    dp[i].append(dp[i-1][i-1] + act * (ind - i + 1))

print(max(dp[n]))

e=enumerate
n,a=open(0)
n=int(n)
d=[0]
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[d[0]+a*(~i-j+n)]+[max(d[k+1]+a*(n+k-i-j),t+a*abs(i-k))for k,t in e(d[:j])]+[d[j]+a*abs(i-j)]
print(max(d))

from operator import itemgetter as get
N = int(input())

A = list(map(int, input().split()))
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev, th, tha):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th-max(l,r)*tha:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s),) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB, SA)]
  pm = M
  SA -= a
  SB -= b

print(pm)


N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]
A.sort(reverse=True)

dp = [[0] * (N + 1) for _ in range(N + 1)]

for s, (a, i) in enumerate(A):
    for l in range(s + 1):
        r = s - l
        L = dp[l][r] + a * (i - (l + 1))
        R = dp[l][r] + a * (N - r - i)

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

ans = 0
for i in range(N + 1):
    ans = max(ans, dp[i][N - i])
print(ans)


from collections import *
from itertools import *

N = int(input())

A = list(map(int, input().split()))
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in list(prev.items()):
    r = k-l
    if p + SB - max(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)


from collections import *
from itertools import *

N = int(input())

A = list(map(int, input().split()))
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in list(prev.items()):
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)


N = int(input())
A = list(map(int, input().split()))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
 
# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x
 
        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))
 
ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)

def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print((sp.join(l)))


def onums(l, sp=" "):
    print((sp.join(map(str, l))))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(n+1):
        for y in range(n+1-x):
            if x == y == 0:
                continue
            ai, i = aii[n-x-y]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1) if x > 0 else 0,
                           dp[x][y-1] + ai * (n-y-i) if y > 0 else 0)

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


def __starting_point():
    n = i1num()
    a = inums()
    aii = sorted((a[i], i)for i in range(n))
    print((solve(n, aii)))

__starting_point()

from operator import itemgetter as get
N = int(input())

A = list(map(int, input().split()))
SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev, th):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s),) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB)]
  pm = M
  SB -= b

print(pm)


from heapq import heappush, heappop
from math import inf

import numpy as np


n = int(input())
A = []
[heappush(A, (-v, i)) for i, v in enumerate(map(int, input().split()), 1)]
dp = np.full((n + 1, n + 1), -inf, dtype=int)
dp[0, 0] = 0

for i in range(n):
    v, j = heappop(A)
    v = -v
    dp[i + 1, 1:] = dp[i, :-1] + v * np.abs(j - np.arange(1, n + 1))
    dp[i + 1, :-1] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(n - i, n + n - i)), dp[i + 1, :-1])

print((dp[-1,].max()))


def f(n, a_list):
    a_list = list(zip(list(range(n)), a_list))
    a_list.sort(key=lambda x: x[1])
    # a_list[j][0]: (j + 1)番目に小さい活発度をもつ幼児の座標
    # a_list[j][1]: ↑の活発度
    dp = [0]
    # dp[x]: x 人を左, (k - x) 人を右に置く場合
    for k in range(1, n + 1):
        dp_ = []
        i, a = a_list.pop()  # i: 座標, a: 活発度
        dp_.append(dp[0] + a * (n - k - i))
        for x in range(1, k):
            dp_.append(max(dp[x - 1] + a * (i - x + 1),
                           dp[x] + a * (n - k + x - i)))
        dp_.append(dp[k - 1] + a * (i - k + 1))
        dp = dp_
    return max(dp)


def __starting_point():
    n = int(input())
    a_list = list(map(int, input().split()))
    print((f(n, a_list)))

__starting_point()

import pprint
N = int(input())
A = list(map(int, input().split()))

def student_sorting(N, A):
    student_list = [0] * N

    for initial_pos, activity in enumerate(A):
        student_list[initial_pos] = (activity, initial_pos)

    return sorted(student_list, reverse = True)

def DP(N, student_list):
    DP_map = list(list(0 for row in range(N + 1 - column)) for column in range(N + 1))
    ans_list = []
    ans = 0

    for left in range(N): #初期値設定 right = 0
        activity = student_list[left][0]
        distance_l = abs(left - student_list[left][1])
        DP_map[left + 1][0] = DP_map[left][0] + activity * distance_l

    for right in range(N): #初期値設定 left = 0
        activity = student_list[right][0]
        distance_r = abs((N - 1 - right) - student_list[right][1])
        DP_map[0][right + 1] = DP_map[0][right] + activity * distance_r

    for left in range(1, N + 1):
        for right in range(1, N - left + 1):
            activity = student_list[left + right - 1][0]
            distance_l = abs((left - 1) - student_list[left + right - 1][1])
            distance_r = abs((N - right) - student_list[left + right - 1][1])
            score_if_appended_to_left = DP_map[left - 1][right] + activity * distance_l
            score_if_appended_to_right = DP_map[left][right - 1] + activity * distance_r
            DP_map[left][right] = max(score_if_appended_to_left, score_if_appended_to_right)

    for left in range(N + 1):
        row = N - left
        column = left
        ans_list.append(DP_map[column][row])

    ans = max(ans_list)

    return ans

student_list = student_sorting(N, A)
ans = DP(N, student_list)
print(ans)


n = int(input())
a = sorted((int(x), k) for k, x in enumerate(input().split()))
opt = [[0 for j in range(n + 1)] for i in range(n + 1)]
for i in reversed(list(range(n))):
    for j in range(i, n):
        val, k = a[j - i]
        opt[i][j] = max(val * abs(k - i) + opt[i + 1][j], val * abs(k - j) + opt[i][j - 1])
print((opt[0][n - 1]))


def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)
 
  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0
 
  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)
 
main()

def solve():
        
    N = int(input())
    A = [(a, i+1) for i, a in enumerate(map(int, input().split()))]

    A.sort(reverse=True)
    INF = float('inf')
    dp = [[-INF] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0

    for s in range(1, N+1):
        for l in range(s+1):
            r = s - l
            dp[l][r] = max(dp[l-1][r] + A[s-1][0] * abs(A[s-1][1]-l), dp[l][r-1] + A[s-1][0] * abs(N-r+1-A[s-1][1]))

    ans = 0
    for m in range(N):
        if dp[m][N-m] > ans:
            ans = dp[m][N-m]

    print(ans)
solve()

# -*- coding: utf-8 -*-


def main():

    # 整数の入力
    a = int(input())
    # # スペース区切りの整数の入力
    nums = list(map(int, input().split()))

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    # dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    # dp = [[0] * a for i in range(a)]

    # cnt = 0
    # dp[i][j]を考える
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            # cnt += 1
            j = k - i + 1
            # if i == 0 and j == 0:
            #     continue

            # 最後の値は場所が特定できるのでそのまま計算させる
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

    # print(cnt)
    print((max([max(x) for x in dp])))


main()


#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], nb: int) -> int:
    s_values = sorted(((v, i) for i, v in enumerate(values)), reverse=True)
    dp = [[0 for _ in range(nb + 1)] for _ in range(nb + 1)]
    for i, (v, p) in enumerate(s_values, start=1):
        for x in range(i + 1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x - 1][0] + abs(p - x + 1) * v
                continue
            if x == 0:
                dp[x][y] = dp[x][y - 1] + abs(nb - y - p) * v
                continue
            dp[x][y] = max(
                dp[x - 1][y] + abs(p - x + 1) * v, dp[x][y - 1] + abs(nb - y - p) * v
            )
    return max(dp[i][nb - i] for i in range(nb + 1))


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print(("Case #{}: {}".format(testcase + 1, result)))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log(log_file: Optional[str] = None) -> None:
    "Configure the log output"
    log_formatter = logging.Formatter(
        "%(asctime)s - %(filename)s:%(lineno)d - " "%(levelname)s - %(message)s"
    )
    if log_file:
        handler = logging.FileHandler(filename=log_file)
    else:
        handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


def __starting_point():
    import doctest

    doctest.testmod()
    return(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

__starting_point()

def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()


# coding: utf-8
N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = [[0] * (N+1) for i in range(N+1)]

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0][i] = dp[0][i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i][0] = dp[i-1][0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x][y]= max(dp[x-1][y] + abs(k-x)*val,
                      dp[x][y-1] + abs(N-y-k+1) * val)

print((int(max(dp[i][N-i] for i in range(N+1)))))


#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

    dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for i in range(N):
        for j in range(0, N - i):
            idx, a = A[i + j]
            #idx = indices[i + j]
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * abs(idx - i))
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * abs(N - 1 - j - idx))
    result = -1
    for i in range(N):
        tmp = dp[i][N - i]
        if tmp > result:
            result = tmp
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


def __starting_point():
    main()

__starting_point()

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

    dp = [[0] * (N + 1) for _ in range(N + 1)]

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

N = int(input())
A = list(map(int, input().split()))
solve(N,A)

#!python3

iim = lambda: list(map(int, input().rstrip().split()))

def resolve():
    N = int(input())
    A = list(enumerate(iim()))

    A.sort(key=lambda x: (x[1], (2*x[0]-N)**2), reverse=True)

    dp = [0] * (N+1)
    dp0 = dp[:]
    for i, (j, ai) in enumerate(A):
        for k in range(i+1):
            dp[k] = max(dp[k], dp0[k] + abs(N-i+k-1-j) * ai)
            dp[k+1] = max(dp[k+1], dp0[k] + abs(k-j) * ai)
        dp, dp0 = dp0, dp

    print((max(dp0)))

def __starting_point():
    resolve()

__starting_point()

N = int(input())
A = list(map(int, input().split()))

A = sorted([(val, pos) for pos, val in enumerate(A)], reverse=True)

dp = [0]
for i, (val, pos) in enumerate(A):
    ldp = [e + val * abs(pos - (i - r)) for r, e in enumerate(dp)]
    rdp = [e + val * abs(N - 1 - r - pos) for r, e in enumerate(dp)]
    dp = [max(L, R) for L, R in zip(ldp + [0], [0] + rdp)]

print((max(dp)))


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

    DP = [[0] * (N + 1) for _ in range(N + 1)]

    for i, b in enumerate(B):
        a = b[0]
        tmp = b[1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

    ans = 0
    for i in range(N + 1):
        ans = max(ans, DP[i][N - i])

    print (ans)

    # for tmp in DP:
    #     print (tmp)

def __starting_point():
    main()
__starting_point()

from heapq import heappush, heappop
from math import inf

import numpy as np


n = int(input())
A = []
[heappush(A, (-v, i)) for i, v in enumerate(map(int, input().split()), 1)]
dp = np.full((n + 1, n + 1), -inf, dtype=int)
dp[0][0] = 0

for i in range(n):
    v, j = heappop(A)
    v = -v
    dp[i + 1, 1:] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(1, n + 1)), dp[i + 1, 1:])
    dp[i + 1, :-1] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(n - i, n + n - i)), dp[i + 1, :-1])

print((dp[-1,].max()))


n,*a = map(int,open(0).read().split())
a = sorted([(j,i) for i,j in enumerate(a)],reverse=True)
dp = [0]
for i,(j,k) in enumerate(a):
  ldp =  [abs(k-i+a)*j+b for a,b in enumerate(dp)]
  rdp =  [abs(n-1-k-a)*j+b for a,b in enumerate(dp)]
  dp = [max(a,b) for a,b in zip(ldp+[0],[0]+rdp)]
print(max(dp))

from collections import *
from itertools import *

N = int(input())

A = list(map(int, input().split()))
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = [0]
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    r = k-l
    if prev[l] + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], prev[l]+abs(N-i-r)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev)

print(prev_max)



N = int(input())

A = list(map(int, input().split()))
AI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev):
  pl, pr, ps = i, 0, 0
  for l, r, s in prev:
    yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
for a,i in AI:
  prev = [*solve(a,i, prev)]

print((max(s for l, r, s in prev)))


N = int(input())
As = list(map(int, input().split()))

dp = [[0] * (N-k+1) for k in range(N+1)]

s = 0
for i, A in sorted(enumerate(As), key = lambda t:t[1], reverse=True):
    s += 1
    for x in range(s+1):
        y = s - x
        if x > 0 and y > 0:
            dp[x][y] = max(dp[x-1][y] + A * (i - x + 1), dp[x][y-1] + A * ((N-y) - i))
        elif x == 0:
            dp[x][y] = dp[x][y-1] + A * ((N-y) - i)
        else:
            dp[x][y] = dp[x-1][y] + A * (i - x + 1)
ans = max((dp[x][N-x] for x in range(N+1)))

print(ans)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(v, i) for i, v in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i, (a, b) in enumerate(AA, start=1):
        for x in range(i+1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x-1][y] + abs(b - x+1) * a
            elif x == 0:
                dp[x][y] = dp[x][y-1] + abs(N-y-b) * a
            else:
                dp[x][y] = max(dp[x-1][y] + abs(b - x + 1) * a, dp[x][y-1] + abs(N-y-b) * a)
    r = 0
    for i in range(N+1):
        r = max(r, dp[i][N-i])
    return r
print((main()))


n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort(reverse=True)

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(n-(j-1) - (i+1))
for k in range(1,n+1): # all go smaller
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1) - (1+(k-1)))

for j in range(1,n+1):
    for k in range(1,n-j+1):
        a, i = A_l[j+k-1]
        j_plus = a*(n-(j-1) - (i+1))
        k_plus = a*((i+1) - (1+(k-1)))
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])


N = int(input())

A = list(map(int, input().split()))
ABI = sorted(((a, max(N-i, i-1)*a, i) for i, a in enumerate(A, 1)), reverse=True)

prev = [0]
for k, (a, b, i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a

  prev = curr

print((max(prev)))


N = int(input())
A = list(map(int, input().split()))

p = list(range(N))
p.sort(key=lambda i: A[i], reverse=True)

dp = [[0]*(N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(i + 1):
        pi = p[i]
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + A[pi]*(N - i + j - 1 - pi))
        dp[i+1][j+1] = dp[i][j] + A[pi]*(pi - j)
print((max(dp[N])))


n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[j] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = [0] * (n + 1)

for i in range(n):
    for j in range(n - i):
        dp[j] = max(dp[j]     + a[p[i]] * abs(p[i] - (j + i)),
                    dp[j + 1] + a[p[i]] * abs(p[i] - j))

print(dp[0])

e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-2**64]*n
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

N = int(input())
A = sorted([(int(x[1]), x[0]) for x in enumerate(input().split())], reverse=True)


V = [0]

for i in range(N-1):
    a, p = A[i]
    s = i+1
    V2 = [None]*(s+1)

    for t in range(s+1):
        v = 0

        if t > 0:
            v = V[t-1] + a*abs(p-(t-1))

        if t < s:
            v = max(V[t] + a*abs(p-(N-s+t)), v)

        V2[t] = v

    V = V2

a, p = A[-1]
for i in range(N):
    V[i] += a*abs(p-i)

print((max(V)))





            


from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))

    a2 = [[a[i], i] for i in range(n)]
    a2.sort(reverse=True)

    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    ans = 0

    for i in range(n + 1):
        for j in range(n + 1 - i):
            s1 = s2 = 0
            if i > 0:
                s1 = dp[i - 1][j] + a2[i + j - 1][0] * (a2[i + j - 1][1] - (i - 1))
            if j > 0:
                s2 = dp[i][j - 1] + a2[i + j - 1][0] * ((n - j) - a2[i + j - 1][1])
            dp[i][j] = max(s1, s2)
        ans = max(ans, dp[i][n - i])

    print(ans)


def __starting_point():
    main()

__starting_point()

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=(a[i],i)
b=sorted(a,reverse=True)
dp=[[-10**14 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    see=b[i-1][0]
    prv=b[i-1][1]
    for j in range(i+1):
        dp[j][i-j]=max(dp[j-1][i-j]+abs(prv-(j-1))*see,dp[j][i-j-1]+abs(n-i+j-prv)*see)
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

n = int(input())
a = list(map(int, input().split()))

p = list(range(n))
p.sort(key=lambda i: a[i])

dp = [0] * (n + 1)

for i in range(n):
    for j in range(n - i):
        dp[j] = max(dp[j]     + a[p[i]] * abs(p[i] - (j + i)),dp[j + 1] + a[p[i]] * abs(p[i] - j))

print((dp[0]))



def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted([(j, i) for i, j in enumerate(a)])[::-1]
    dp = [0]
    for i in range(n):
        dp2 = [0]*(i+2)
        A, p = a[i]
        for j in range(i+1):
            right = n-i-1+j
            dp2[j] = max(dp2[j], dp[j]+abs(p-right)*A)
            dp2[j+1] = max(dp2[j+1], dp[j]+abs(p-j)*A)
        dp = dp2
    print((max(dp2)))


main()


n=int(input())
a=list(map(int,input().split()))
l=[]
for i,x in enumerate(a):
    l.append([x,i])
l.sort(reverse=True)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i,j in l:
    for x in range(cnt+1):
        if x==0:
            dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
        elif x==cnt:
            dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
        else:
            dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
    cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

from collections import *
from itertools import *

N = int(input())

A = list(map(int, input().split()))
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  for l, p in list(prev.items()):
    r = k-l
    if p + SB - max(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev.values())

print(prev_max)


def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print((sp.join(l)))


def onums(l, sp=" "):
    print((sp.join(map(str, l))))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = dp[x-1][0] + ai * (i-x+1)
        dp[0][x] = dp[0][x-1] + ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1),
                           dp[x][y-1] + ai * (n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


def __starting_point():
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print((solve(n, aii)))

__starting_point()

def main():
    import numpy as np
    n=int(input())
    a=list(enumerate(map(int,input().split())))
    a.sort(key=lambda x: -x[1])
    dp=[np.zeros(i+1,dtype=np.int64) for i in range(n+1)]
    dp[0]=np.zeros(1,dtype=np.int64)
    r=np.arange(n+1,dtype=np.int64)
    for time,ix in enumerate(a):
        i,x=ix
        dp[time+1][1:]=dp[time][:time+1]+(i-r[:time+1])*x
        np.maximum(dp[time+1][:-1],dp[time]+((n-1-(time-r[:time+1]))-i)*x,out=dp[time+1][:-1])
    print(np.max(dp[n]))
main()

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])

def __starting_point():
      input = sys.stdin.readline
      n=int(input())
      a_=list(map(int,input().split()))
      print((f(n,a_)))

__starting_point()

from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
import numpy as np
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)
print((max(dp[n])))


n = int(input())
a = [(_a, i) for i, _a in enumerate(map(int, input().split()))]
a.sort(reverse=True)

dp = [[0]*(n+1) for _ in range(n+1)]
for i, (v, p) in enumerate(a):
    # 前にj人いる
    dp[i+1][0] = dp[i][0] + v*abs((n-1 - i) - p)
    for j in range(1, i+1):
        dp[i+1][j] = max(dp[i][j] + v*abs((n-1 - (i-j)) - p),
                         dp[i][j-1] + v*abs((j-1) - p))
    dp[i+1][i+1] = dp[i][i] + v*abs(i - p)
print((max(dp[n])))


def main():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[0] * (N+1-i) for i in range(N+1)]

    A = list(enumerate(A))
    A.sort(key=lambda x: x[1])
    ans = 0
    for z in range(1, N+1):
        tmp = A.pop()
        i = tmp[0]+1
        a = tmp[1]
        for x in range(z+1):
            y = z - x
            if x == 0:
                dp[x][y] = max(dp[x][y-1]+a*abs(i-(N-y+1)), dp[x][y])
            elif y == 0:
                dp[x][y] = max(dp[x-1][y]+a*abs(i-x), dp[x][y])
            else:
                dp[x][y] = max(dp[x][y-1]+a*abs(i-(N-y+1)), dp[x][y], dp[x-1][y]+a*abs(i-x))
            ans = max(ans, dp[x][y])
    print(ans)

def __starting_point():
    main()

__starting_point()

import numpy as np

n = int(input())
A = list(map(int, input().split()))

babies = sorted([(activity, index) for index, activity in enumerate(A, 1)], reverse=True)

DP = np.zeros(n+1, dtype=np.int64)
position = np.arange(1, n+1, dtype=np.int64)

for filled, (activity, index) in enumerate(babies, 1):
    to_left = DP[:filled] + abs((position[:filled]-index)*activity)
    to_right = DP[:filled] + abs((position[-filled:]-index)*activity)
    DP[1:filled+1] = np.maximum(DP[1:filled+1], to_left)
    DP[:filled] = np.maximum(DP[:filled], to_right)

print((DP.max()))


# import time
# p0 = time.time()

N = int(input())
A = list(map(int,input().split()))
# print(A)
A = [[A[i],i] for i in range(N)]
A.sort(reverse=True)
# print("A :",A)
dp = [[0]*(N+1) for _ in range(N+1)]
# print(dp)

#dp[x][y] : x人は Ai*(i-pi),y人は Ai*(pi-i)
#           piは 0,1,2...   piはN-1,N-2,N-3,,
# p1 = time.time()-p0

dp[0][0] = 0
# y = 0
for x in range(1,N+1):
    dp[x][0] = dp[x-1][0]+A[x-1][0]*(A[x-1][1]-x+1)
    # print(x,dp)
# x = 0
for y in range(1,N+1):
    dp[0][y] = dp[0][y-1]+A[y-1][0]*(N-y - A[y-1][1])
    # print(x,dp)

# p2 = time.time()-p0
for x in range(1,N):
    for y in range(1,N+1-x):
        A0 = A[x+y-1][0]
        A1 = A[x+y-1][1]
        dp[x][y] = max(dp[x-1][y] + A0*(A1+1 - x), dp[x][y-1] + A0*(N-y - A1))
# print(dp)

# p3 = time.time()-p0

c = 0
for i in range(N):
    if c < dp[i][N-i]:
        c = dp[i][N-i]
print(c)

# print(p1,p2,p3)


def main():
    N, *A = map(int, open(0).read().split())

    A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for l in range(N):
        for r in range(N - l):
            p, a = A[l + r]

            dp[l + 1][r] = max(
                dp[l + 1][r],
                a * (p - l) + dp[l][r]
            )
            dp[l][r + 1] = max(
                dp[l][r + 1],
                a * (N - 1 - r - p) + dp[l][r]
            )

    print(max(dp[l][N - l] for l in range(N)))

main()

N = int(input())
A = list(map(int, input().split()))
table = []

for i, a in enumerate(A):
    table.append([a,i])
table.sort()

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))

ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)



def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted([(a, i) for i, a in enumerate(A)], reverse=True)

    # dp[i][j] := A が大きい順に i + j 個について、i 個を左詰めして、j 個を右詰めしたときのスコア
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        j = 0
        while i+j < N:
            a, idx = A[i+j]
            # 左に詰める場合
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (idx - i) * a)
            # 右に詰める場合
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + ((N-1-j) - idx) * a)
            j += 1
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i][N-i])
    print(ans)


def __starting_point():
    resolve()
__starting_point()

import sys
sys.setrecursionlimit(2000 * 2)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

def main():
    from random import sample
    from operator import itemgetter
    e=enumerate
    n,a=open(0)
    n=int(n)
    d=[0]+[-2**64]*n
    for j,(a,i)in e(sorted(sample([(a,i)for i,a in e(map(int,a.split()))],n),key=itemgetter(0),reverse=1)):
        d=[max(t+a*(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
    print(max(d))
main()

n=int(input())
a=list(map(int,input().split()))
a=list(zip(list(range(n)),a))#[index,a]の配列
a.sort(key=lambda x:x[1])#aの昇順で並べる
dp=[[0 for i in range(n+1)]for j in range(n+1)] #dp[x][y]:=左にx、右にy人並べたときの最大値
ans=0
for k in range(n):# k人目まで終了、k+1人目に対して
  i,ai=a.pop()#aの大きいものから取り出す
  dp[k+1][0]=dp[k][0]+ai*(i-k)
  dp[0][k+1]=dp[0][k]+ai*(n-k-1-i)
  for l in range(k):#右にl+1人並べたとき
    dp[k-l][l+1]=max(dp[k-l-1][l+1]+ai*(i-k+l+1),dp[k-l][l]+ai*(n-l-1-i))
for k in range(n+1):
  ans=max(ans,dp[k][n-k])

print(ans)



def main():

  n = int(input())
  arr = list(map(int, input().split()))
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print((max(dp[n])))

main()


# coding: utf-8
# Your code here!
#import numpy as np
N = int(input())
A = list(map(int,input().split()))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = [[0for i in range(N+1)]for j in range(N+1)]
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]= max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(int(max(dp[k][N-k] for k in range(N+1))))

def main():
    N, *A = map(int, open(0).read().split())

    A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i, (p, a) in enumerate(A):
        for j in range(i + 1):
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a * (p - j))
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * (N - (i - j) - 1 - p))

    print(max(dp[N]))

main()

def main():
    import numpy as np
    n=int(input())
    a=list(enumerate(map(int,input().split())))
    a.sort(key=lambda x: -x[1])
    dp=[np.zeros(i+1,dtype=np.int64) for i in range(n+1)]
    dp[0]=np.zeros(1,dtype=np.int64)
    r=np.arange(n+1,dtype=np.int64)
    for time,ix in enumerate(a):
        i,x=ix
        dp[time+1][1:]=dp[time][:time+1]+(i-r[:time+1])*x
        dp[time+1][:-1]=np.maximum(dp[time+1][:-1],dp[time]+((n-1-(time-r[:time+1]))-i)*x)
    print(np.max(dp[n]))
main()

def main():
    from operator import itemgetter
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    AP = []
    for i in range(N):
        AP.append((A[i], i))
    AP.sort(key=itemgetter(0), reverse=True)

    # dp[i][l][r]
    # 大きい方からi個まで左右を決めて
    # 左をl回、右をr回使ったときの最大値
    # r = i - l
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        ai, pi = AP[i]
        for l in range(i+1):
            r = i - l
            # 左
            if dp[i+1][l+1] < dp[i][l] + (pi-l)*ai:
                dp[i+1][l+1] = dp[i][l] + (pi-l)*ai
            # 右
            if dp[i+1][l] < dp[i][l] + ((N-r-1)-pi)*ai:
                dp[i+1][l] = dp[i][l] + ((N-r-1)-pi)*ai

    print(max(dp[N]))

main()

#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))

    A = sorted(enumerate(A), key = lambda x: x[1])[::-1]

    #dp = np.zeros((N+1,N+1), dtype='int64')
    dp = [[0]*(N+1-i) for i in range(N+1)]

    m = 0
    for i in range(1,len(A)+1):
        index,a = A[i-1]
        for j in range(i+1):
            if (i-j,j) == (0,0):
                dp[i-j][j] = 0
            elif i-j == 0:
                dp[i-j][j] = dp[i-j][j-1] + (N-j-index)*a
            elif j == 0:
                dp[i-j][j] = dp[i-j-1][j] + (abs(index-(i-j-1)))*a
            else:
                dp[i-j][j] = max(dp[i-j][j-1] + (N-j-index)*a, dp[i-j-1][j] + (abs(index-(i-j-1)))*a)
            if i == len(A):
                m = max(m, dp[i-j][j])

    #print(dp)
    #print(np.max(dp))
    print(m)

main()


n = int(input())
xs = list(enumerate(map(int, input().split())))
xs.sort(key=lambda x: x[1])
xs.reverse()

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    (j, a) = xs[i - 1]

    for x in range(0, i + 1):
        y = i - x
        if x == 0:
            dp[x][y] = dp[x][y - 1] + a * (n - y - j)
        elif y == 0:
            dp[x][y] = dp[x - 1][y] + a * (j - x + 1)
        else:
            dp[x][y] = max(dp[x][y - 1] + a * (n - y - j),
                    dp[x - 1][y] + a * (j - x + 1))

print(max([dp[i][n - i] for i in range(n + 1)]))

N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, i) for i, a in enumerate(A)], reverse=True)

dp = [0] * (N + 1)
for i in range(N):
    dp2 = dp[:]
    for l in range(i + 1):
        a, pos = A[i]
        # add left side
        dp2[l + 1] = max(dp2[l + 1], dp[l] + (pos - l) * a)
        # add right side
        r = i - l + 1
        dp2[l] = max(dp2[l], dp[l] + (N - r - pos) * a)
    dp = dp2
print(max(dp))

def main():
    N = int(input())
    A = list(map(int, input().split()))

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        a = sortedA[i][0]
        idx = sortedA[i][1]
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+a*abs((N-r-1)-idx))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+a*abs(l-idx))
    print((max(dp[N])))

main()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(a, i) for i, a in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        a, t = AA[i]
        for x in range(i + 2):
            y = i + 1 - x
            dp[x][y] = max((dp[x - 1][y] + abs(t - (x - 1)) * a) if x > 0 else 0,
                           (dp[x][y - 1] + abs(t - (N - y)) * a) if y > 0 else 0)
    return max(dp[i][N - i] for i in range(N + 1))

print((main()))


N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield p+abs(j-i)*a, s+abs(j+r)*a
    p = s
  yield s+abs(len(prev)-i)*a,

pd = [0]
A = list(map(int, input().split()))
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*list(map(max, solve(a,i, pd)))]

print((max(pd)))


N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = list(map(int, input().split()))
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, pd)]

print((max(pd)))


N = int(input())

def left(a, i, prev):
  yield 0
  for l, s in enumerate(prev, 1-i):
    yield s+abs(l)*a
    
def right(a, i, prev):
  for r, s in enumerate(prev, N - len(prev) - i + 1):
    yield s+abs(r)*a
  yield 0

pd = [0]
A = list(map(int, input().split()))
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*list(map(max, list(zip(left(a,i, pd), right(a,i, pd)))))]

print((max(pd)))


import heapq
import time
st = time.time()
n = int(input())
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))
dp = [[0 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*(n-1-hi)
dp[1][1] = -ai*hi
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(n-i-hi)
    dp[i][i] = dp[i-1][i-1] - ai*abs(hi-i+1)
    for j in range(1,i):
        dp[i][j] = max(dp[i-1][j-1]-ai*abs(hi-j+1),dp[i-1][j]-ai*abs(n-i+j-hi))

print((max(dp[n])))


N = int(input())
A = list(map(int,input().split()))
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a, i) in enumerate(ABI):
    curr = [0]*(k+2)
    for l in range(k+1):
        curr[l] = max(curr[l], prev[l] + a*abs(N-i-(k-l)))
        curr[l+1] = prev[l]+a*abs(i-l-1)
    prev = curr
print (max(prev))

from operator import itemgetter

def main():
    n = int(input())
    a = sorted(enumerate(map(int, input().split())), key=itemgetter(1), reverse=True)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for x in range(n):
        for y in range(n - x):
            i, ai = a[x + y]
            dp[x + 1][y] = max(ai * (i - x) + dp[x][y], dp[x + 1][y])
            dp[x][y + 1] = max(ai * (n - 1 - y - i) + dp[x][y], dp[x][y + 1])
    print(max(dp[i][n - i] for i in range(n)))

def __starting_point():
    main()
__starting_point()

#!python3

# input
N = int(input())
A = list(map(int, input().split()))
# N = 2000
# A = [i for i in range(1, N + 1)]


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(list(range(1, N + 1)), P):
        x, y = p
        for i in range(n):
            j = n - 1 - i
            left = dp[i][j] + x * abs(y - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            right = dp[i][j] + x * abs(y - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'e1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

inf = 10 ** 9
inf = 10 ** 3

def solve():
    n = read_int()
    a = read_int_list()
    b = [(a[i], i) for i in range(n)]
    b.sort()
    best = [[-inf] * (n + 1) for i in range(n + 1)]
    best[0][0] = 0
    for s in range(1, n + 1):
        for x in range(s + 1):
            y = s - x
            ai, i = b[-s]
            if x > 0:
                c = best[x - 1][y] + (n - x) * ai - i * ai
                if c > best[x][y]:
                    best[x][y] = c
            if y > 0:
                c = best[x][y - 1] - (y - 1) * ai + i * ai
                if c > best[x][y]:
                    best[x][y] = c

    # for i in range(n + 1):
    #     for j in range(n + 1):
    #         print(best[i][j], end='\t')
    #     print()

    res = - inf
    for x in range(n):
        y = n - x
        if res < best[x][y]:
            res = best[x][y]
    return res


def main():
    res = solve()
    print(res)


def __starting_point():
    main()

__starting_point()

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]

N = int(input())
#X, Y = map(int,input().split())
A = list(map(int,input().split()))

B = []
for i in range(N):
    B.append([A[i], i])
B.sort(reverse=True)

#dp = [[0 for _ in range(N+2)] for _ in range(N+2)]
#for x in range(1,N+2):
#    for y in range(1,N+2):
##        print(act,i)
#        dp[x][y] = max(dp[x-1][y] + B[y][0] * (B[y][1] - 0 - (x-2))
#                    , dp[x][y-1] + B[y][0] * (N - 1 - B[y][1] - (y-2)))
        
dp = np.zeros(1, dtype=int)
zero = np.zeros(1, dtype=int)
for act, i in B:
    prev = dp.copy()
    dp = np.append(dp,[0])
    l = len(prev)
        
    right = np.arange((N-1-i)*act,(N-1-i)*act - (act*(l)),-act)
    left = np.arange(i*act-(act*(l-1)),(i+1)*act,act)
#    print(left,right,prev,dp)
    np.maximum(np.concatenate([prev + left, zero]),
               np.concatenate([zero, prev + right]),
               out = dp)
#    print(dp)

print(np.max(dp))

n = int(input())
a = list(map(int, input().split()))

a = list(enumerate(a))
a.sort(key = lambda x: x[1])

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    pos, val = a.pop()
    pos = pos + 1

    DP[0][i] = DP[0][i-1] + abs(val * (n - i + 1 - pos))
    DP[i][0] = DP[i-1][0] + abs(val * (pos - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(val * (pos - x)),  \
            DP[x][y-1] + abs(val * (n - y + 1 - pos)))

ans = 0
for i in range(n+1):
    ans = max(ans, DP[i][n-i])

print(ans) 

# -*- coding: utf-8 -*-

import math
    
def abs(num):
    if num < 0:
        return -num
    else:
        return num

def abc163e(n, a):
    hap_dict = dict()
    hap_list = []
    for elem in range(n):
        if a[elem] in hap_dict:
            hap_dict[a[elem]].append(elem)
        else:
            tmp_list = [elem]
            hap_dict[a[elem]] = tmp_list
            hap_list.append(a[elem])
    
    hap_list.sort(reverse=True)

    left = 0
    right = n-1

    num = 0
    dp = [[0 for re in range(n+1)] for le in range(n+1)]
    for hap in hap_list:
        pos_list = hap_dict[hap]

        while len(pos_list) != 0:
            tgt = pos_list.pop()

            num += 1

            for left in range(num+1):
                right = num-left
                if left == num: # left end
                    dp[left][right] = dp[left-1][right] + hap * abs(tgt-left+1)
                elif left == 0: # right end
                    dp[left][right] = dp[left][right-1] + hap * abs(n-right-tgt)
                else:
                    left_dp = dp[left-1][right] + hap * abs(tgt-left+1)
                    right_dp = dp[left][right-1] + hap * abs(n-right-tgt)
                    dp[left][right] = max(left_dp, right_dp)
                #print("[",str(left),"][",str(right),"]=",str(dp[left][right]))

    ans_list = []
    for i in range(num+1):
        ans_list.append(dp[i][num-i])
    return max(ans_list)

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    a = list(map(int, input().split(" ")))

    ans = abc163e(n, a)

    # output
    print(ans)
    
# else:
    # do nothing


def main():
	n, *a = list(map(int, open(0).read().split()))
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for t, (c, k) in enumerate(sorted((c, k) for k, c in enumerate(a))[::-1]):
		for i in range(t + 1):
			j = t - i
			if dp[i + 1][j] <= (s := dp[i][j] + c * abs(i - k)): dp[i + 1][j] = s
			if dp[i][j + 1] <= (s := dp[i][j] + c * abs(n - 1 - k - j)): dp[i][j + 1] = s
	print((max(dp[i][~i] for i in range(n + 1))))

def __starting_point():
	main()

__starting_point()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    AA=[(v,i) for i,v in enumerate(A)]
    AA.sort(reverse=True)
    dp=[[0]*(N+1) for _ in range(N+1)]
    for len in range(1,N+1):
        val,index=AA[len-1]
        for x in range(0,len+1):
            y=len-x
            if x==0:
                dp[x][y]=dp[x][y-1]+val*abs(N-y-index)
            elif y==0:
                dp[x][y]=dp[x-1][y]+val*abs(index-x+1)
            else:
                dp[x][y]=max(dp[x][y-1]+val*abs(N-y-index),dp[x-1][y]+val*abs(index-x+1))
    maxes=[]
    for i in dp:
        maxes.append(max(i))
    return max(maxes)
print(main())

N = int(input())
A = [int(s) for s in input().split(" ")]
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a,i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    
  prev = curr

print(max(prev))


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted([(a, i) for i, a in enumerate(A)], reverse=True)

    # dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i, (a, p) in enumerate(A):
        for j in range(i + 1):
            # 左に詰める場合
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (p - j) * a)
            # 右に詰める場合
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ((N - (i - j) - 1) - p) * a)

    print(max(dp[-1]))


def __starting_point():
    resolve()
__starting_point()