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

m = {}
for x, c in enumerate(l):
    if c in m:
        m[c].append(x)
    else:
        m[c] = [x]

s = {(0, n): 0}
result = 0

def add(new, l, r, v):
    # print("adding: ", l, r, v)
    if l == r:
        # print("here")
        global result
        result = max(result, v)
        return
    if (l, r) in new:
        new[(l, r)] = max(new[(l, r)], v)
    else:
        new[(l, r)] = v
        

m = list(sorted(list(m.items()), reverse=True))
for c, posx in m:
    rposx = list(reversed(posx))
    z = len(posx)
    new = {}
    for (left, right), value in s.items():
        # print("abc: ", left, right, value, rposx)
        l = left + z
        r = right
        d0 = sum((abs(left+i-x) for i, x in enumerate(rposx)))
        # print("do: ", d0)
        add(new, l, r, value + d0*c)
        for i, x in enumerate(posx):

            l -= 1
            r -= 1
            d0 = d0 - abs(l - x) + abs(r - x)
            

            # print("d0: ", d0)
            add(new, l, r, value + d0*c)
    s = new
    
print(result)