from sys import stdin

N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

#greedyに解けるか?
#greedyで解けるならば計算量はN**2
#N<2000なので行ける1

selected = []

happy_sum = 0
for i in range(N):

    #まず左端から処理をする
    max_happy_l1 = 0
    max_happy_l2 = 0
    max_happy_pos_l1 = -1
    max_happy_pos_l2 = -1
    for j in range(N):
        if j in selected:
            continue
        #移動距離 |i-j|*Ajが最高になるjを選ぶ
        distance = abs(i-j)
        if max_happy_pos_l1>=0:
            if max_happy_l1 + As[max_happy_pos_l1] < As[j]*distance  + As[j]:
                max_happy_l2 = max_happy_l1
                max_happy_pos_l2 = max_happy_pos_l1
                max_happy_l1 = As[j]*distance
                max_happy_pos_l1 = j
        else:
            if max_happy_l1 < distance*As[j]: 
                max_happy_l2 = max_happy_l1
                max_happy_pos_l2 = max_happy_pos_l1
                max_happy_l1 = distance*As[j]
                max_happy_pos_l1=j


    max_happy_r1 = 0
    max_happy_r2 = 0
    max_happy_pos_r1 = -1
    max_happy_pos_r2 = -1

    #次に右端から見ていく
    for j in range(N):
        if j in selected:
            continue
        #移動距離 |i-j|*Ajが最高になるjを選ぶ
        distance = abs((N-i-1)-j)
        if max_happy_pos_r1>=0:
            if max_happy_r1 + As[max_happy_pos_r1] < As[j]*distance  + As[j]:
                max_happy_r2 = max_happy_r1
                max_happy_pos_r2 = max_happy_pos_r1
                max_happy_r1 = As[j]*distance
                max_happy_pos_r1 = j
        else:
            if max_happy_r1 < distance*As[j]: 
                max_happy_r2 = max_happy_r1
                max_happy_pos_r2 = max_happy_pos_r1
                max_happy_r1 = distance*As[j]
                max_happy_pos_r1=j


    if len(selected) == N-1:
        happy_sum += max_happy_l1
        break

    if max_happy_pos_l1 == max_happy_pos_r1: #左右で同じものが選ばれた場合
        if max_happy_l1>=max_happy_r1:
            happy_sum+= (max_happy_l1 + max_happy_r2)
            selected.append(max_happy_pos_l1)
            selected.append(max_happy_pos_r2)
        else:
            happy_sum+= (max_happy_l2 + max_happy_r1)
            selected.append(max_happy_pos_l2)
            selected.append(max_happy_pos_r1)
    else:
            happy_sum+= (max_happy_l1 + max_happy_r1)
            selected.append(max_happy_pos_l1)
            selected.append(max_happy_pos_r1)

    if len(selected) == N:
        break


print(happy_sum) 