CodeEff/ECCO huggingface dataset:
# Original solution

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

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

inds=sorted(list(range(len(As))), key=lambda k: As[k])[::-1]

ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds[0][0]=0
for i in range(1,N+1):
    ds[i][0]=ds[i-1][0]+As[inds[i-1]]*(inds[i-1]-(i-1))
    ds[0][i]=ds[0][i-1]+As[inds[i-1]]*(N-i-inds[i-1])

for xy in range(2,N+1):
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1][y]+As[inds[xy-1]]*(inds[xy-1]-(x-1))
        c2=ds[x][y-1]+As[inds[xy-1]]*(N-y-inds[xy-1])
        ds[x][y]=max(c1,c2)

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




# Optimized solution

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

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

inds=sorted(list(range(len(As))), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+As[inds[xy-1]]*(inds[xy-1]-(xy-1))
    nds[0]=ds[0]+As[inds[xy-1]]*(N-xy-inds[xy-1])

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+As[inds[xy-1]]*abs(inds[xy-1]-(x-1))
        c2=ds[x]+As[inds[xy-1]]*abs(N-y-inds[xy-1])
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print((max(ds)))
#print(ds)
#print(inds)
# Original solution

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

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

inds=sorted(list(range(len(As))), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+As[inds[xy-1]]*(inds[xy-1]-(xy-1))
    nds[0]=ds[0]+As[inds[xy-1]]*(N-xy-inds[xy-1])

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+As[inds[xy-1]]*abs(inds[xy-1]-(x-1))
        c2=ds[x]+As[inds[xy-1]]*abs(N-y-inds[xy-1])
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print((max(ds)))
#print(ds)
#print(inds)




# Optimized solution

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

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

inds=sorted(list(range(len(As))), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1]
    a=As[i]
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print((max(ds)))
#print(ds)
#print(inds)
# Original solution
import sys

from functools import lru_cache

sys.setrecursionlimit(2 * 10 ** 5)

N = int(eval(input()))

A = [int(x) for x in input().split()]
A = sorted((a, i) for i, a in enumerate(A))


@lru_cache(maxsize=None)
def dp(l, r):
    if l > r:
        return 0
    a, x = A[r - l]
    return max(a * abs(x - l) + dp(l + 1, r), a * abs(x - r) + dp(l, r - 1))


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

# Optimized solution
import sys

sys.setrecursionlimit(2 * 10 ** 5)

N = int(eval(input()))

A = [int(x) for x in input().split()]
A = sorted((a, i) for i, a in enumerate(A))

cache = [[None for i in range(N + 1)] for j in range(N + 1)]


def dp(l, r):
    if l > r:
        return 0
    if cache[l][r] is None:
        a, x = A[r - l]
        cache[l][r] = max(a * abs(x - l) + dp(l + 1, r), a * abs(x - r) + dp(l, r - 1))
    return cache[l][r]


print((dp(0, N - 1)))
# Original solution
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(eval(input()))
a = list(map(int, input().split()))
a = [(item, i) for i,item in enumerate(a)]
s = sorted(a)[::-1] # (value, index)
dp = [[None] * (n+1) for _ in range(n+1)] # 高い方からx+y人について、a_i * (p_i - i) + a_i * (i - p_i) の和の最大値

dp[0][0] = 0
tmp = 0
# dp[x][y] : 右にx個、左にy個
for i in range(n):
    val, ind = s[i]
    dp[i+1][0] = dp[i][0] + val * ((n-i-1) - ind)
for i in range(n):
    val, ind = s[i]
    dp[0][i+1] = dp[0][i] + val * (ind - i)

for i in range(2,n+1):
    for x in range(1,i):
        y = i - x
        val, ind = s[i-1]
        v1 = dp[x-1][y] + val * ((n-1 - (x-1)) - ind)
        v2 = dp[x][y-1] + val * (ind - (y-1))
        dp[x][y] = max(v1, v2)
print((max((dp[x][n-x] for x in range(n+1)))))

# Optimized solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(eval(input()))
a = list(map(int, input().split()))
a = [(num,i) for i,num in enumerate(a)]
a.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    for j in range(n-i+1):
        if i>0:
            dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i+j-1][0]*abs(a[i+j-1][1]-(i-1)))
        if j>0:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + a[i+j-1][0]*abs(a[i+j-1][1]-(n-j)))
ans = max(dp[i][n-i] for i in range(n+1))
print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
L=[]
for i in range(N):
    L.append([A[i],i])
#print(L)
ans=0
import copy
from collections import deque
for i in range(1,N):
    cnt=0
    a=copy.deepcopy(L[:i])
    b=copy.deepcopy(L[i:])
    #print(a,b)
    a.sort(reverse=True)
    b.sort(reverse=True)
    #print("ab",a,b)
    A=deque([N-len(a)+j for j in range(len(a)) ])
    B=deque([j for j in range(len(b))])
    #print(A)
    #print(B)
    for j in range(len(a)):
        if abs(a[j][0]*(a[j][1]-A[0]))>abs(a[j][0]*(a[j][1]-A[-1])):
            cnt+=abs(a[j][0]*(a[j][1]-A[0]))
            A.popleft()
        else:
            cnt+=abs(a[j][0]*(a[j][1]-A[-1]))
            A.pop()
    #print("A",cnt)
    for j in range(len(b)):
        if abs(b[j][0]*(b[j][1]-B[0]))>abs(b[j][0]*(b[j][1]-B[-1])):
            cnt+=abs(b[j][0]*(b[j][1]-B[0]))
            B.popleft()
        else:
            cnt+=abs(b[j][0]*(b[j][1]-B[-1]))
            B.pop()
    #print(cnt)
    if ans<cnt:
        ans=cnt
print(ans)


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

L=[[10**10,0]]
for i in range(N):
    L.append([A[i],i])
L.sort(reverse=True)
#print(L)
DP=[[0 for i in range(N+1)]for j in range(N+1)]
#j=右に押し込んだ数
for i in range(1,N+1):
    for j in range(i+1):
        if j==0:
            DP[i][j]=DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1))
            #print(DP,DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1)))
        elif j==i:
            DP[i][j]=DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j))
            #print(DP,DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
        else:
            DP[i][j]=max(DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
            #print(DP,DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
print((max(DP[-1])))
# Original solution
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    A_ = []
    indices = []
    tmp = sorted(enumerate(A), reverse=True, key=lambda x:x[1])
    for row in tmp:
        k, v = row
        indices.append(k)
        A_.append(v)
    A = A_
    
    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):
            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)

if __name__ == '__main__':
    main()


# Optimized solution
#!/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)


if __name__ == '__main__':
    main()
# Original solution
# from pprint import pprint
n = int(eval(input()))
a = list(map(int, input().split()))
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print((max(dp[i][n-i] for i in range(n+1))))


# Optimized solution
#  from pprint import pprint
n = int(eval(input()))
a = list(map(int, input().split()))
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print((max(dp[i][n-i] for i in range(n+1))))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append([v, i])
b.sort(reverse = True)
dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

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

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

print(ans)

# Optimized solution
import sys
input = sys.stdin.buffer.readline

n = int(eval(input()))
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append([v, i])
b.sort(reverse = True)
dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

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

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

print(ans)
# Original solution
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))))

# Optimized solution
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]<dp[i][j]+c*abs(i-k):dp[i+1][j]=dp[i][j]+c*abs(i-k)
		if dp[i][j+1]<dp[i][j]+c*abs(n-1-k-j):dp[i][j+1]=dp[i][j]+c*abs(n-1-k-j)
print((max(dp[i][~i]for i in range(n+1))))
# Original solution
#!python3

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


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):
        for i in range(n):
            j = n - 1 - i

            left = dp[i][j] + p[0] * abs(p[1] - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            
            right = dp[i][j] + p[0] * abs(p[1] - (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)


if __name__ == "__main__":
    main()


# Optimized solution
#!python3

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


if __name__ == "__main__":
    main()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

B = [[i, a] for i, a in enumerate(A)]

C = sorted(B, key=lambda b: b[1], reverse=True)

l = 0
r = N - 1

ans = 0
queue = [[C, l, r, 0]]
while queue:
    D, l, r, total = queue.pop()

    total2 = total + abs(D[0][0] - l) * D[0][1]
    if len(D) == 1:
        ans = max(ans, total2)
        continue
    else:
        queue.append([D[1:], l+1, r, total2])

    total2 = total + abs(D[0][0] - r) * D[0][1]
    if len(D) == 1:
        ans = max(ans, total2)
        continue
    else:
        queue.append([D[1:], l, r-1, total2])

print(ans)


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

B = [[i, a] for i, a in enumerate(A)]

C = sorted(B, key=lambda b: b[1], reverse=True)

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

dp[1][0] = (C[0][0] - 0) * C[0][1]
dp[0][1] = ((N - 1) - C[0][0]) * C[0][1]

ans = 0
for i in range(2, N + 1):
    for j in range(0, i + 1):
        t1, t2 = 0, 0

        if j - 1 >= 0:
            t1 = dp[j - 1][i - j] + abs((C[i - 1][0] - (j - 1))) * C[i - 1][1]

        if i - j - 1 >= 0:
            t2 = dp[j][i - j - 1] + abs((C[i - 1][0] - (N - (i - j)))) * C[i - 1][1]

        dp[j][i - j] = max(t1, t2)

        if i == N:
            ans = max(ans, dp[j][i - j])

print(ans)
# Original solution
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [[a,i] for i,a in enumerate(LI())]
data.sort(reverse=True)

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

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


# Optimized solution
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [(a,i) for i,a in enumerate(LI())]
data.sort(reverse=True)

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

for i in range(N):
    a, p = data[i]
    for j in range(i+1):
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + abs(N-1-j-p)*a)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + abs(i-j-p)*a)
print((max(dp[-1])))
# Original solution
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [(a,i) for i,a in enumerate(LI())]
data.sort(reverse=True)

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

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


# Optimized solution
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [[a,i] for i,a in enumerate(LI())]
data.sort(reverse=True)

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

for i in range(N):
    a, p = data[i]
    for j in range(i+1):
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + abs(N-1-j-p)*a)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + abs(i-j-p)*a)
print((max(dp[-1])))
# Original solution
from collections import defaultdict

n=int(eval(input()))
a_=list(map(int,input().split()))
#n=4
#a_=[1,3,4,2]
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)


# Optimized solution
from collections import defaultdict
n=int(eval(input()))
a_=list(map(int,input().split()))
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)
# Original solution
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

data = [(a,i) for i,a in enumerate(A)]
data.sort(reverse = True)

dp = [[0] * (n+1) for i in range(n+1)]
for i in range(n):
  for l in range(i+1):
    r = i-l
    dp[l+1][r] = max(dp[l+1][r], dp[l][r] + data[i][0] * abs(data[i][1] - l))
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + data[i][0] * abs(data[i][1]-(n-1-r)))  

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


# Optimized solution
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

data = [(ai,i) for i,ai in enumerate(A)]
data.sort(reverse = True)

dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n):
  for l in range(i+1):
    r = i-l
    dp[l+1][r] = max(dp[l+1][r], dp[l][r] + data[i][0] * abs(data[i][1] - l))
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + data[i][0] * abs(data[i][1] - (n-1-r)))

ans = 0
for i in range(n):
  ans = max(ans,dp[i][n-i])
print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))

babies=[(a,i) for i,a in enumerate(a)]
babies.sort(reverse=True)

dp=[[0]*(n+1) for i in range(n+1)]#左、右から何人いるか? 家庭菜園
ans=0
for l in range(n):
    for r in range(n):
        if l+r==n:
            ans=max(ans,dp[l][r])
            break
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[r+1][r],dp[l][r]+abs(ind-l)*activeness)
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)

print(ans)


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

babies=[(a,i) for i,a in enumerate(a)]
babies.sort(reverse=True)

dp=[[0]*(n+1) for i in range(n+1)]#左、右から何人いるか dpはl,r埋まってるときの最大スコア 家庭菜園
ans=0
for l in range(n):
    for r in range(n):
        if l+r==n:
            ans=max(ans,dp[l][r])
            break
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[l+1][r],dp[l][r]+abs(ind-l)*activeness)#左を埋める
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)#右を埋める

print(ans)
# Original solution
e=enumerate
n,*a=list(map(int,open(0).read().split()))
d=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):d=[d[0]+a*(~i-j+n)]+[max(d[k]+a*(~i-j+n+k),d[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[d[j]+a*abs(i-j)]
print((max(d)))

# Optimized solution
e=enumerate
n,*a=list(map(int,open(0).read().split()))
d=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):d=[d[0]+a*(~i-j+n)]+[max(d[k+1]+a*(n+k-i-j),d[k]+a*abs(i-k))for k in range(j)]+[d[j]+a*abs(i-j)]
print((max(d)))
# Original solution
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-9e18]*n
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[max(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k)if k else 0)for k,t in e(d)]
print((max(d)))

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

# Optimized solution
n=int(eval(input()))
d=[0]+[-10**18]*n
for j,(a,i)in enumerate(sorted((-a,i)for i,a in enumerate(map(int,input().split())))):
    d=[max(t-a*abs(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in enumerate(d)]
print((max(d)))
# Original solution
e=enumerate
n,a=open(0)
d=[0]+[-2**64]*2000
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*(~i-j+k+int(n)),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print((max(d)))

# Optimized solution
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(list(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()
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        if i+j<=n and (i>0 or j>0):
            v=b[i+j-1][0]
            pos=b[i+j-1][1]
            if i==0:
                dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
            elif j==0:
                dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
            else:
                dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1-i):
        if i+j==0:
            continue
        v=b[i+j-1][0]
        pos=b[i+j-1][1]
        if i==0:
            dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
        elif j==0:
            dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
        else:
            dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)