N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: -x[1])

scores = []
for i in range(N):
    arr = [(As[j] * abs(i-j), j) for j in range(N)]
    arr.sort()
    scores.append(arr)

dp = {}
dp[(0, N-1)] = [0, set()]
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        tmpl = tmplidx = lsc = tmpr = tmpridx = rsc = 0
        if l > 0:
            # l-1, r から
            lsc, lst = dp[(l-1, r)]
            il = -1
            while True:
                tmpl, tmplidx = scores[l-1][il]
                if tmplidx in lst:
                    il -= 1
                else:
                    break
        if r < N-1:
            # l, r+1 から
            rsc, rst = dp[(l, r+1)]
            ir = -1
            while True:
                tmpr, tmpridx = scores[r+1][ir]
                if tmpridx in rst:
                    ir -= 1
                else:
                    break
        if lsc + tmpl > rsc + tmpr:
            ndp[(l, r)] = [lsc+tmpl, lst|{tmplidx}]
        else:
            ndp[(l, r)] = [rsc+tmpr, rst|{tmpridx}]
    dp = ndp
print(max([s for s, st in dp.values()]))