CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(eval(input()))
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = dict()
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if (l, r) in dp:
        return dp[(l, r)]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[(l, r)] = res
    return res
ans = dfs(0, n-1)
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(eval(input()))
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)
# Original solution
from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = {}
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    T = l, i
    if T in DP:
        return DP[T]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[T] = max(v1, v2)
    return DP[T]

print((opt(0, 0)))


# Optimized solution
from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = [[-1]*N for _ in range(N)]
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    if DP[i][l] != -1: return DP[i][l]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[i][l] = max(v1, v2)
    return DP[i][l]

print((opt(0, 0)))
# Original solution
import itertools
n = int(eval(input()))
A = list(map(int, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = abs(i-j)*A[i-1]
ans = 0
for x in itertools.permutations(list(range(1, n+1)), n):
    cnt = 0
    for i, j in enumerate(x):
        cnt += dp[i+1][j]
    ans = max(ans, cnt)
print(ans)


# Optimized solution
n = int(eval(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)]
ans = 0
for L in range(n+1):
    for R in range(n+1):
        if n <= L+R-1:
            continue
        a, i = A[L+R-1]
        if 0 <= R-1:
            dp[L][R] = max(dp[L][R], dp[L][R-1]+abs((n-R)-i)*a)
        if 0 <= L-1:
            dp[L][R] = max(dp[L][R], dp[L-1][R]+abs(i-(L-1))*a)
        ans = max(ans, dp[L][R])
print(ans)
# Original solution
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(eval(input()))
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n=inp()
a = inpl()
sorted_a = sorted(a,reverse=True)
place=defaultdict(lambda: [])
for i in range(n):
    place[a[i]].append(i+1)
ans = 0
dp=[[-INF]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    if i!=0 and sorted_a[i] == sorted_a[i - 1]:
        index += 1
    else:
        index = 0
    for j in range(n):
        _place = place[sorted_a[i]][index]
        #右
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + sorted_a[i] * abs(n - (i - j) - _place))
        #左
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + sorted_a[i] *  abs(_place - j - 1))

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

# Optimized solution
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(eval(input()))
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n=inp()
a = inpl()
sorted_a = sorted(a,reverse=True)
place=dict()
for i in range(n):
    if a[i] not in place:
        place[a[i]]=[i+1]
    else:
        place[a[i]].append(i+1)
ans = 0
dp=[[-INF]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    if i!=0 and sorted_a[i] == sorted_a[i - 1]:
        index += 1
    else:
        index = 0
    for j in range(n):
        _place = place[sorted_a[i]][index]
        #右
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + sorted_a[i] * abs(n - (i - j) - _place))
        #左
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + sorted_a[i] *  abs(_place - j - 1))

print((max(dp[n])))
# Original solution
from collections import *
from itertools import *

N = int(eval(input()))

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

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

print(curr_max)


# Optimized solution
from collections import *
from itertools import *

N = int(eval(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)
# Original solution
from collections import *
from itertools import *

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


# Optimized solution
from collections import *
from itertools import *

N = int(eval(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)
# Original solution
from collections import *
from itertools import *

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


# Optimized solution
N = int(eval(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)))
# Original solution
from operator import itemgetter as get
N = int(eval(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)


# Optimized solution

N = int(eval(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)))
# Original solution
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
b = []
for i in range(n):
    b.append((a[i],i))

b.sort(reverse=True)

ans = 0

def f(left,right,k,c):
    if k == n:
        return c
    i,j = b[k]
    x = abs(j-left)
    y = abs(right-j)
    return max(f(left+1,right,k+1,c+x*i), f(left,right-1,k+1,c+y*i))

ans = f(0,n-1,0,0)

print(ans)


# Optimized solution
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
b = []
for i in range(n):
    b.append((a[i],i))
 
b.sort(reverse=True)

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

for i in range(1,n+1):
    x,y = b[i-1]
    for j in range(i+1):
        left = dp[i-1][j-1] + x*abs(y-j+1) if j > 0 else -1
        right = dp[i-1][j] + x*abs(n-i+j-y) if j < i else -1
        dp[i][j] = max(left,right)

print((max(dp[-1])))
# Original solution
import itertools

N=int(eval(input()))
actlist=list(map(int,input().split()))
alllist=list(itertools.permutations(list(range(1,N+1))))

count=1
l=len(alllist)
maxnum=0

for i in range(0,l-1):
    for j in range(i+1,l):
        hapsum=0
        for m,n in zip(alllist[i],alllist[j]):
            hapsum+=actlist[m-1]*abs(m-n)
        if maxnum<hapsum:
            maxnum=hapsum
        
print(maxnum)

# Optimized solution
N=int(eval(input()))
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

INF = float('inf')
left=1
right=N
maxnum=0

dp = [[-INF] * (N+1) for _ in range(N+1)]
        
for r in range(N+1):
    for l in range(N-r+1):
        if r==0 and l==0:
            dp[l][r]=0
        else:
            dp[l][r]=max(dp[l][r-1]+As[l+r-1][0]*abs(N-r-As[l+r-1][1]),\
              dp[l-1][r]+As[l+r-1][0]*abs(l-1-As[l+r-1][1]))
            maxnum=dp[l][r] if maxnum<dp[l][r] else maxnum

print(maxnum)
# Original solution
N=int(eval(input()))
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

INF = float('inf')
left=1
right=N
maxnum=0

dp = [[-INF] * (N+1) for _ in range(N+1)]
        
for r in range(N+1):
    for l in range(N-r+1):
        if r==0 and l==0:
            dp[l][r]=0
        else:
            dp[l][r]=max(dp[l][r-1]+As[l+r-1][0]*abs(N-r-As[l+r-1][1]),\
              dp[l-1][r]+As[l+r-1][0]*abs(l-1-As[l+r-1][1]))
            maxnum=dp[l][r] if maxnum<dp[l][r] else maxnum

print(maxnum)

# Optimized solution
def main():
  N = int(eval(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()
# Original solution
import sys
n = int(eval(input()))
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


sys.setrecursionlimit(2010)
print((dfs(0, n-1)))


# Optimized solution
import sys
import time

t = time.time()

n = int(eval(input()))
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))
# print(time.time()-t)

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


sys.setrecursionlimit(2010)
print((dfs(0, n-1)))
# Original solution
import functools
import sys

sys.setrecursionlimit(10 ** 9)

eval(input())

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))


@functools.lru_cache(maxsize=None)
def dp(l, r, idx):
    if idx == len(arr):
        return 0

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    return max(left, right)


print((dp(0, len(arr) - 1, 0)))


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 9)

eval(input())

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))

d = [[-1 for _ in range(len(arr))] for _ in range(len(arr))]


def dp(l, r, idx):
    if idx == len(arr):
        return 0

    if d[l][r] != -1:
        return d[l][r]

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    d[l][r] = max(left, right)
    return max(left, right)


print((dp(0, len(arr) - 1, 0)))
# Original solution
from heapq import heappop, heappush
from collections import defaultdict

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

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in list(dp.items()):
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = 0
for k, v in list(dp.items()):
    ans = max(ans, v)

print(ans)


# Optimized solution
from heapq import heappop, heappush
from collections import defaultdict

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

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in list(dp.items()):
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = max(dp.values())

print(ans)
# Original solution
N = int(eval(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,,
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)
    
for x in range(1,N):
    for y in range(1,N+1-x):
        dp[x][y] = max(dp[x-1][y] + A[x+y-1][0]*(A[x+y-1][1]+1 - x), dp[x][y-1] + A[x+y-1][0]*(N-y - A[x+y-1][1]))
# print(dp)

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

# Optimized solution
# import time
# p0 = time.time()

N = int(eval(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)
# Original solution
def main():
  N = int(eval(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()


# Optimized solution
def solve():
        
    N = int(eval(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()
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
ma=max(a)
l=[[] for _ in range(ma+1)]
chk=[0]*n
ans=0
for i,x in enumerate(a):
    l[x].append(i)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(ma,0,-1):
    for j in l[i]:
        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)

# Optimized solution
n=int(eval(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)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

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

a = [list(a[i]) for i in range(n)]
a = [[a[i][0]+1, a[i][1]] for i in range(n)]

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):
    DP[0][i] = DP[0][i-1] + abs(a[i-1][1] * (n - i + 1 - a[i-1][0]))
    DP[i][0] = DP[i-1][0] + abs(a[i-1][1] * (a[i-1][0] - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(a[i-1][1] * (a[i-1][0] - x)),  \
            DP[x][y-1] + abs(a[i-1][1] * (n - y + 1 - a[i-1][0])))

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

print(ans) 

# Optimized solution
n = int(eval(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)
# Original solution
#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = {}
DP[(0, 0)] = 0

for wa in range(1, N+1):
    # AA[:wa]までを考える
    a, i = AA[wa-1]
    for x in range(wa+1):
        y = wa - x
        DP[(x, y)] = 0
        if x - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x-1, y)]+a*(i-x))
        if y - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x, y-1)]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

print((max([DP[(x, N-x)] for x in range(N+1)])))


# Optimized solution
#!/usr/bin/env python3
import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

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

for wa in range(1, N+1):
    # AA[:wa]までを考える
    for x in range(wa+1):
        y = wa - x
        a, i = AA[wa-1]
        if x - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x-1][y]+a*(i-x))
        if y - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x][y-1]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

M = -INF
for x in range(N):
    y = N-x
    M = max(DP[x][y], M)
print(M)