# -*- 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人を右から活性度順に並べた状態の(スコア最大値, 移動済のもの)をタプル化したものとする
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にした場合
        res[1][0] = (max_num * max(max_num_idxes), [(max(max_num_idxes), max_num)])
        # x,y = 0,1にした場合
        res[0][1] = (max_num * (a - 1 - min(max_num_idxes)), [(min(max_num_idxes), max_num)])

        # print(res[1][0][0])
        # print(res[0][1][0])
    elif i == 2:
        # x,y = 2,0にした場合
        nums_clone = nums.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]
        res[2][0] = (max_num * abs(max(max_num_idxes) - 1) + res[1][0][0], res[1][0][1] + [(max(max_num_idxes), max_num)])

        # x,y = 0,2にした場合
        nums_clone = nums.copy()
        for x in res[0][1][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]
        res[0][2] = (max_num * abs(a - 1 - min(max_num_idxes) - 1) + res[0][1][0], res[0][1][1] + [(min(max_num_idxes), max_num)])

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

        # x,y = 1,1にした場合
        # from 1,0
        nums_clone = nums.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]
        from_1_0 = (max_num * abs(a - 1 - min(max_num_idxes)) + res[1][0][0], res[1][0][1] + [(min(max_num_idxes), max_num)])
        # from 0,1
        nums_clone = nums.copy()
        for x in res[0][1][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]
        from_0_1 = (max_num * abs(max(max_num_idxes)) + res[0][1][0], res[0][1][1] + [(max(max_num_idxes), max_num)])
        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 = nums.copy()
        for x in res[i-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]
        res[i][0] = (max_num * abs(max(max_num_idxes) - (i - 1)) + res[i-1][0][0], res[i-1][0][1] + [(max(max_num_idxes), max_num)])

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

        # x,y = 0,iにした場合
        nums_clone = nums.copy()
        for x in res[0][i-1][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]
        res[0][i] = (max_num * abs(a - 1 - min(max_num_idxes) - (i - 1)) + res[0][i-1][0], res[0][i-1][1] + [(min(max_num_idxes), max_num)])

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

        # x,y = j,i-jにした場合
        for j in range(1, i):
            # from j-1,i-j
            nums_clone = nums.copy()
            for x in res[j-1][i-j][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]
            # 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(max(max_num_idxes) - (j-1)) + res[j-1][i-j][0], res[j-1][i-j][1] + [(max(max_num_idxes), max_num)])
            # from j,i-j-1
            nums_clone = nums.copy()
            for x in res[j][i-j-1][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]
            # 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 - min(max_num_idxes) - (i-j-1)) + res[j][i-j-1][0], res[j][i-j-1][1] + [(min(max_num_idxes), max_num)])
            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))