CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort()
A_l.reverse()

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

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        a, i = A_l[j+k-1]
        j_plus = a*(yb-(i+1))
        k_plus = a*((i+1)-ys)
        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])

# Optimized solution
n = int(eval(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])
# Original solution
# coding: utf-8
N = int(eval(input()))
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = [[0 for _ in range(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((k-x >= 0)*(dp[x-1][y] + (k-x)*val),
                     (N-y-k+1 >= 0)*(dp[x][y-1] + (N-y-k+1) * val))

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


# Optimized solution
# coding: utf-8
N = int(eval(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)))))
# Original solution
'''
着想：大きい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)
'''

N = int(eval(input()))
A = [[a, i] for a,i in zip(list(map(int, input().split())), list(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))))

# Optimized solution
'''
着想：大きい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(eval(input()))
  A = [[a, i] for a,i in zip(list(map(int, input().split())), list(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()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

A = list(enumerate(A, start=1))
A.sort(reverse=True, key=lambda x: x[1])

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


# Optimized solution
N = int(eval(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])))
# Original solution
#def solve():
INF = float('inf')

def max2(x, y): return x if x >= y else y

N = int(eval(input()))
As = [(A, i) for i, A in enumerate(map(int, input().split()))]

As.sort(reverse=True)

dp = [[-INF]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for no, (A, pos) in enumerate(As):
    for i in range(no+1):
        j = no-i
        dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
        dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))

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

print(ans)
 
 
#solve()

# Optimized solution
def solve():
    INF = float('inf')
 
    def max2(x, y): return x if x >= y else y
 
    N = int(eval(input()))
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]
 
    As.sort(reverse=True)
 
    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))
 
    ans = 0
    for i in range(N+1):
        j = N-i
        ans = max2(ans, dp[i][j])
 
    print(ans)
 
 
solve()
# Original solution
import heapq
n = int(eval(input()))
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))

dp = [[-1 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*hi
dp[0][1] = -ai*(n-1-hi)
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(hi-i+1)
    dp[0][i] = dp[0][i-1] - ai*abs(n-i-hi)
    for j in range(1,i):
        dp[i-j][j] = max(dp[i-j-1][j]-ai*abs(hi-i+j+1),dp[i-j][j-1]-ai*abs(n-j-hi))

max = 0
for i in range(n+1):
    if max < dp[i][n-i]:
        max = dp[i][n-i]
print(max)


# Optimized solution
import heapq
import time
st = time.time()
n = int(eval(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])))
# Original solution
import sys
sys.setrecursionlimit(10 ** 9)

N = int(eval(input()))
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [{} for _ in range(N)]


def search(i, l):
    # i番目の幼児を見ていて左にl人配置している
    if i == N:
        return 0
    if l in dp[i]:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print((search(0, 0)))

# Optimized solution
import sys
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]


def search(i, l):
    # i番目の幼児を見ていて左にl人配置している
    if i == N:
        return 0
    if dp[i][l] != -1:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print((search(0, 0)))
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(eval(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 in range(N):
        a = B[i][0]
        tmp = B[i][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)

if __name__ == '__main__':
    main()

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

    N = int(eval(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)

if __name__ == '__main__':
    main()
# Original solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
@lru_cache(maxsize=None)
def rec(l, r):
	if l > r:
		return 0
	idx = r-l  # 次に選ぶ幼児
	val, i = L[idx]
	ret = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return ret

print((rec(0, N-1)))


# Optimized solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
dp = [[-1]*N for _ in range(N)]

def rec(l, r):
	if l > r:
		return 0
	if dp[l][r] >= 0:
		return dp[l][r]
	idx = r-l  # 次に選ぶ幼児
	val, i = L[idx]
	dp[l][r] = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return dp[l][r]

print((rec(0, N-1)))
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
ans = [[0 for i in range(n+1)] for j in range(n+1)]
p = []
for i in range(n):
    p.append([a[i],i])
p.sort(reverse=True)

for i in range(1,n+1):
    ans[0][i] = ans[0][i-1] + p[i-1][0]*abs(p[i-1][1]-i+1)
for i in range(1,n+1):
    ans[i][0] = ans[i-1][0] + p[i-1][0]*abs(n-i-p[i-1][1])

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

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

# Optimized solution
#pythonじゃ通らなかった…(´・ω・`)
n = int(eval(input()))
a = list(map(int,input().split()))
ans = [[0 for i in range(n+1)] for j in range(n+1)]
p = []

#それぞれの活発度と元々居た位置の記録
for i in range(n):
    p.append([a[i],i])
p.sort(reverse=True)

#活発度の高い順にそれぞれ左と右から詰めて並べていく時のうれしさの変化
for i in range(1,n+1):
    ans[0][i] = ans[0][i-1] + p[i-1][0]*abs(p[i-1][1]-i+1)
for i in range(1,n+1):
    ans[i][0] = ans[i-1][0] + p[i-1][0]*abs(n-i-p[i-1][1])

#Douteki Planning 活発度の高い順に左にi人、右にj人詰めて並べていった時の最大値
for i in range(1,n):
    for j in range(1,n-i+1):
        ans[i][j] = max(ans[i][j-1] + p[i+j -1][0]*abs(p[i+j -1][1]-j+1),
        ans[i-1][j] + p[i+j - 1][0]*abs(n-i-p[i+j-1][1]))

#全て詰め並べ終わったときのうれしさの最大値(=答え)を探す
ma = 0
for i in range(n):
    ma = max(ma,ans[0+i][n-i])
print(ma)
# Original solution
#!python3
import sys
sys.setrecursionlimit(1000000000)
from functools import lru_cache

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

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

    A.sort(key=lambda x: x[1], reverse=True)

    @lru_cache
    def rec(i, j1, j2):
        if i == N:
            return 0
        pos, ai = A[i]

        ax = abs(pos - j1) * ai + rec(i+1, j1+1, j2)
        bx = abs(pos - j2) * ai + rec(i+1, j1, j2-1)

        return max(ax, bx)

    print((rec(0, 0, N-1)))

if __name__ == "__main__":
    resolve()


# Optimized solution
#!python3

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

def resolve():
    N = int(eval(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)))

if __name__ == "__main__":
    resolve()
# Original solution
N = int(eval(input()))
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(list(range(0, i+1))):
        dp[j] = max((dp[j-1]+a*abs(x-(j-1)))*(j-1>=0), (dp[j]+a*abs(N-(i-j)-x))*(j<=i-1))
print((max(dp)))

# Optimized solution
N = int(eval(input()))
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(list(range(0, i+1))):
        dp[j] = max((dp[j-1]+a*(x-(j-1)))*(j-1>=0), (dp[j]+a*(N-(i-j)-x))*(j<=i-1))
print((max(dp)))
# Original solution
N = int(eval(input()))
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(list(range(0, i+1))):
        res1 = dp[j-1]+a*(x-(j-1))*(j-1>=0)
        res2 = dp[j]+a*(N-(i-j)-x)*(j<=i-1)
        if res1>=res2: dp[j] = res1
        else: dp[j] = res2
print((max(dp)))

# Optimized solution
N = int(eval(input()))
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(list(range(i))):
        dp[j+1] = max(dp[j] + a*(x-j), dp[j+1])
        dp[j] += a*(N-(i-j)-x)
print((max(dp)))
# Original solution
N = int(eval(input()))
a = list(map(int, input().split()))

A =[] 

for i in range(N):
  A.append([i+1,a[i]])


A.sort(key=lambda x: x[1], reverse=True)


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


for i in range(N+1):
  for x in range(i+1):
    y = i - x
    if x == 0 and y == 0:
      dp[x][y] = 0
    
    elif x == 0:
      dp[x][y] = dp[x][y-1] + A[y-1][1]*((N-y+1) - (A[y-1][0]))


    elif y == 0:
      dp[x][y] = dp[x-1][y] + A[x-1][1]*((A[x-1][0]) - x )


    else:
      dp[x][y] = max(dp[x][y-1] + A[x+y-1][1]*((N-y+1) - (A[x+y-1][0])) , dp[x-1][y] + A[x+y-1][1]*((A[x+y-1][0]) - x ))

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

# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))

A =[] 

for i in range(N):
  A.append([i+1,a[i]])


A.sort(key=lambda x: x[1], reverse=True)

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

for i in range(N+1):
  for x in range(i+1):
    y = i - x
    if x == 0 and y == 0:
      dp[x][y] = 0
    
    elif x == 0:
      dp[x][y] = dp[x][y-1] + A[y-1][1]*((N-y+1) - (A[y-1][0]))


    elif y == 0:
      dp[x][y] = dp[x-1][y] + A[x-1][1]*((A[x-1][0]) - x )


    else:
      dp[x][y] = max(dp[x][y-1] + A[x+y-1][1]*((N-y+1) - (A[x+y-1][0])) , dp[x-1][y] + A[x+y-1][1]*((A[x+y-1][0]) - x ))

ans = 0
for x in range(N+1):
  y = N - x
  ans = max(ans,dp[x][y])
  
print(ans)
# Original solution
N = int(eval(input()))
_L = list(map(int,input().split()))

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:(-x[0],-x[1]))

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

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print((max(dp[-1])))




# Optimized solution
N = int(eval(input()))
_L = list(map(int,input().split()))

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:(-x[0],x[1]))

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

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print((max(dp[-1])))
# Original solution
N = int(eval(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
        dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + a * (i - (l + 1)))
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a * (N - r - i))

ans = max([max(d) for d in dp])
print(ans)


# Optimized solution
N = int(eval(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
        dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + a * (i - (l + 1)))
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a * (N - r - i))

ans = 0
for i in range(N + 1):
    ans = max(ans, dp[i][N - i])
print(ans)
# Original solution
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,*A = get_all_int()

# dp[i][j] = 活発度高い順のi人目まで処理し、左にjに置いた場合のうれしさの最大
dp = [ [0] * (n+1) for _ in range(n+1) ]

AA = list(enumerate(A))
AA.sort(key=(lambda t: t[1]), reverse=True)

for i, t in enumerate(AA):
    # k 移動前の位置
    # a 活発度
    k,a = t
    for j in range(i+1):
        # 左に置く (すでに左端にj人居る)
        move = abs(k - j)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a*move)

        # 右に置く (すでに右端にi-j人居る)
        move = abs(k - (n-(i-j)-1))
        dp[i+1][j] =   max(dp[i+1][j],   dp[i][j] + a*move)

ans = 0

for j in range(n+1):
    ans = max(ans, dp[n][j])

# left = 0
# right = n-1

# AA = list(enumerate(A))
# AA.sort(key=(lambda t: t[1]), reverse=True)
# ans = 0
# for i,a in AA:
#     log(i,a)
#     l = abs(left-i)
#     r = abs(right-i)

#     if l > r:
#         log(f"  {i}->{left}, ", a*l)
#         ans += a * l
#         left += 1
#     else:
#         log(f"  {i}->{right}, ", a*r)
#         ans += a * r
#         right -= 1

print(ans)


# Optimized solution
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return list(map(int, open(0).read().split()))

n,*A = get_all_int()

# dp[i][j] = 活発度高い順のi人目まで処理し、左にjに置いた場合のうれしさの最大
dp = [ [0] * (n+1) for _ in range(n+1) ]

AA = list(enumerate(A))
AA.sort(key=(lambda t: t[1]), reverse=True)

for i, t in enumerate(AA):
    # k 移動前の位置
    # a 活発度
    k,a = t
    for j in range(i+1):
        # 左に置く (すでに左端にj人居る)
        move = abs(k - j)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a*move)

        # 右に置く (すでに右端にi-j人居る)
        move = abs(k - (n-(i-j)-1))
        dp[i+1][j] =   max(dp[i+1][j],   dp[i][j] + a*move)

ans = 0

for j in range(n+1):
    ans = max(ans, dp[n][j])

print(ans)
# Original solution
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for s in range(1, N+1):
        for x in range(s):
            for y in range(s-x):
                i, d = A[x+y]
                dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
                dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()

# Optimized solution
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for x in range(N):
        for y in range(N-x):
            i, d = A[x+y]
            dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
            dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()