### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
strs = input().split()

nums = []
for i in range(a):
    nums.append((i, int(strs[i])))

# print(nums)

# res[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態の(スコア最大値, 移動済のものを除いたnums)とする
res = []
for i in range(a+1):
    ls = []
    for j in range(a+1):
        ls.append((0, []))
    res.append(ls)

for i in range(a+1):
    # print("i in range(a)")
    # print(i)
    # print(a)
    # print("i in range(a)")
    if i == 0:
        continue
    if i == 1:
        max_num = max([x[1] for x in nums])
        max_num_idxes = [x[0] for x in nums if x[1] == max_num]
        # x,y = 1,0にした場合
        nums_clone = nums.copy()
        nums_clone.remove((max(max_num_idxes), max_num))
        res[1][0] = (max_num * max(max_num_idxes), nums_clone)
        # x,y = 0,1にした場合
        nums_clone = nums.copy()
        nums_clone.remove((min(max_num_idxes), max_num))
        res[0][1] = (max_num * (a - 1 - min(max_num_idxes)), nums_clone)

        # print(res[1][0][0])
        # print(res[0][1][0])
    elif i == 2:
        # x,y = 2,0にした場合
        nums_clone = res[1][0][1].copy()
        # for x in res[1][0][1]:
        #     nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((max(max_num_idxes), max_num))
        res[2][0] = (max_num * abs(max(max_num_idxes) - 1) + res[1][0][0], nums_clone)

        # x,y = 0,2にした場合
        nums_clone = res[0][1][1].copy()
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((min(max_num_idxes), max_num))
        res[0][2] = (max_num * abs(a - 1 - min(max_num_idxes) - 1) + res[0][1][0], nums_clone)

        # print(res[2][0][0])
        # print(res[0][2][0])

        # x,y = 1,1にした場合
        # from 1,0
        nums_clone = res[1][0][1].copy()
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((min(max_num_idxes), max_num))
        from_1_0 = (max_num * abs(a - 1 - min(max_num_idxes)) + res[1][0][0], nums_clone)
        # from 0,1
        nums_clone = res[0][1][1].copy()
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((max(max_num_idxes), max_num))
        from_0_1 = (max_num * abs(max(max_num_idxes)) + res[0][1][0], nums_clone)
        if from_1_0[0] < from_0_1[0]:
            res[1][1] = from_0_1
        else:
            res[1][1] = from_1_0

        # print(res[1][1][0])

    else:
        # x,y = i,0にした場合
        nums_clone = res[i-1][0][1].copy()
        max_num = max([x[1] for x in nums_clone])
        target_idx = max([x[0] for x in nums_clone if x[1] == max_num])
        nums_clone.remove((target_idx, max_num))
        res[i][0] = (max_num * abs(target_idx - (i - 1)) + res[i-1][0][0], nums_clone)

        # print(res[i][0][0])

        # x,y = 0,iにした場合
        nums_clone = res[0][i-1][1].copy()
        max_num = max([x[1] for x in nums_clone])
        target_idx = min([x[0] for x in nums_clone if x[1] == max_num])
        nums_clone.remove((target_idx, max_num))
        res[0][i] = (max_num * abs(a - 1 - target_idx - (i - 1)) + res[0][i-1][0], nums_clone)

        # print(res[0][i][0])

        # x,y = j,i-jにした場合
        for j in range(1, i):
            # from j-1,i-j
            nums_clone = res[j-1][i-j][1].copy()
            max_num = max([x[1] for x in nums_clone])
            target_idx = max([x[0] for x in nums_clone if x[1] == max_num])
            nums_clone.remove((target_idx, max_num))
            # from_a = (max_num * abs(a - 1 - min(max_num_idxes) - (i-j-1)) + res[j-1][i-j][0], res[j-1][i-j][1] + [(min(max_num_idxes), max_num)])
            from_a = (max_num * abs(target_idx - (j-1)) + res[j-1][i-j][0], nums_clone)
            # from j,i-j-1
            nums_clone = res[j][i-j-1][1].copy()
            max_num = max([x[1] for x in nums_clone])
            target_idx = min([x[0] for x in nums_clone if x[1] == max_num])
            nums_clone.remove((target_idx, max_num))
            # from_b = (max_num * abs(max(max_num_idxes) - (j-1)) + res[j][i-j-1][0], res[j][i-j-1][1] + [(max(max_num_idxes), max_num)])
            from_b = (max_num * abs(a - 1 - target_idx - (i-j-1)) + res[j][i-j-1][0], nums_clone)
            if from_a < from_b:
                res[j][i-j] = from_b
            else:
                res[j][i-j] = from_a
            # print(res[j][i-j][0])

    if i == a:
        result = []
        for j in range(a+1):
            result.append(res[j][i-j][0])
        # print(result)
        print(max(result))

### FIXED CODE ###

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


def main():

    # 整数の入力
    a = int(input())
    # # スペース区切りの整数の入力
    nums = list(map(int, input().split()))

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    # dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    # dp = [[0] * a for i in range(a)]

    # cnt = 0
    # dp[i][j]を考える
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            # cnt += 1
            j = k - i + 1
            # if i == 0 and j == 0:
            #     continue

            # 最後の値は場所が特定できるのでそのまま計算させる
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

    # print(cnt)
    print(max([max(x) for x in dp]))


main()