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

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

sorted_nums = sorted(only_nums, reverse=True)
# print(sorted_nums)

# 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 = sorted_nums[0]
        sorted_nums = sorted_nums[1:]
        # x,y = 0,1にした場合
        max_num_idx_min = -1
        nums_clone = nums.copy()
        for x in nums_clone:
            if x[1] == max_num:
                max_num_idx_min = x[0]
                break
        nums_clone[max_num_idx_min] = (nums_clone[max_num_idx_min][0], nums_clone[max_num_idx_min][1], False)
        res[0][1] = (max_num * (a - 1 - max_num_idx_min), nums_clone)

        # x,y = 1,0にした場合
        max_num_idx_max = -1
        nums_clone = nums.copy()
        nums_clone.reverse()
        for x in nums_clone:
            if x[1] == max_num:
                max_num_idx_max = x[0]
                break
        nums_clone.reverse()
        nums_clone[max_num_idx_max] = (nums_clone[max_num_idx_max][0], nums_clone[max_num_idx_max][1], False)
        res[1][0] = (max_num * max_num_idx_max, 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])

        # print(sorted_nums)
        max_num = sorted_nums[0]
        sorted_nums = sorted_nums[1:]
        # x,y = i-j,j(0 ≤ j ≤ i)にした場合を考える
        # i - 1のresについてそれぞれ次の状態を考えていく
        # res[i-1][0], res[i-2][1], res[i-3][2], ... , res[i-1-j][j], ... , res[0][i-1]
        ls_j = []
        for j in range(i):
            # from i-j-1,j to i-j,j (最大活性のものを左に移動)
            max_num_idx_max = -1
            nums_clone = res[i - j - 1][j][1].copy()
            nums_clone.reverse()
            for x in nums_clone:
                if x[1] == max_num and x[2]:
                    max_num_idx_max = x[0]
                    break
            nums_clone.reverse()
            score_left = max_num * abs(max_num_idx_max - (i - j - 1)) + res[i - j - 1][j][0]
            nums_clone[max_num_idx_max] = (nums_clone[max_num_idx_max][0], nums_clone[max_num_idx_max][1], False)
            left = (score_left, nums_clone)
            # res[j-1][i-j+1] = (score_left, nums_clone)

            # from i-j-1,j to i-j-1,j+1 (最大活性のものを右に移動)
            max_num_idx_min = -1
            nums_clone = res[i - j - 1][j][1].copy()
            for x in nums_clone:
                if x[1] == max_num and x[2]:
                    max_num_idx_min = x[0]
                    break
            score_right = max_num * abs(a - 1 - max_num_idx_min - j) + res[i - j - 1][j][0]
            nums_clone[max_num_idx_min] = (nums_clone[max_num_idx_min][0], nums_clone[max_num_idx_min][1], False)
            right = (score_right, nums_clone)
            # res[j-1][i-j+1] = (score_right, nums_clone)

            ls_j.append((left, right))

        # iのres (res[i-j][j]) についてそれぞれleftとrightのどちらがより高いスコアかを考えて値を決定する
        for j in range(i + 1):
            # i,0は決定済
            if j == 0:
                res[i - j][j] = ls_j[0][0]
            # 0,iは決定済
            elif j == i:
                res[i - j][j] = ls_j[i - 1][1]
            else:
                # 木のイメージで左側から伸びてきた枝
                from_left = ls_j[j - 1][1]
                # 木のイメージで右側から伸びてきた枝
                from_right = ls_j[j][0]
                if from_left[0] < from_right[0]:
                    res[i - j][j] = from_right
                else:
                    res[i - j][j] = from_left
            #
            # 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))