n = int(input())
a = list(map(int,input().split()))
a_sort = sorted(a)
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang_, pos_):
    pos = pos_.copy()
    rang = rang_.copy()
    ret= 0 
    while pos != []:
        if abs(rang[0]-pos[-1]) < abs(rang[-1]-pos[0]):
            ret += abs(rang[-1]-pos[0])
            del rang[-1]
            del pos[0]
        else:
            ret += abs(rang[0]-pos[-1]) 
            del rang[0]
            del pos[-1]
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    #print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                    #print(j,acm,dp[j][acm])
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))