N = int(input())
A = list(map(int, input().split()))
A_ans, ori, ans = [A[0]], [0], 0

def switch(i, a):
    gain, index = 0, i
    for j in range(i):
        temp = A_ans[j]*((i - ori[j]) - abs(j - ori[j])) + a*(i - j)
        if gain < temp:
            gain, index = temp, j
    return index, gain

def push_away(i, a):
    gain = [0]
    for j in range(1, i+1):
        gain.append(a + gain[j-1])
        k = i - j
        gain[j] += (2 * int(ori[k] < k + 1) - 1) * A_ans[k]
    index = gain.index(max(gain))

    return index, gain[index]

for i in range(1, N):
    a = A[i]
    i_s, g_s = switch(i, a)
    i_p, g_p = push_away(i, a)

    if g_s > g_p:
        ans += g_s
        A_ans.append(A_ans[i_s])
        A_ans[i_s] = a
        ori.append(ori[i_s])
        ori[i_s] = i
    else:
        ans += g_p        
        index = i - i_p
        A_ans = A_ans[:index] + [a] + A_ans[index:]
        ori = ori[:index] + [i] + ori[index:]
print(ans)