
import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]

N = int(input())
#X, Y = map(int,input().split())
A = list(map(int,input().split()))

left = [0]
right = [0]
ans = 0
for i in range(N):
    l, r = 0, 0
    for j in range(len(left)):
        if A[i] > left[j]:
            buff = i - len(left) + 1 if left[j] == 0 else 1
            l += (A[i] - left[j]) * buff
        else:
            break
    for j in range(len(right)):
        if A[i] > right[j]:
            buff = N-i-1 - len(right) + 1 if right[j] == 0 else 1
            r += (A[i] - right[j]) * buff
        else:
            break
    if r > l:
        right.append(A[i])
        right.sort()
        ans += r
    else:
        left.append(A[i])
        left.sort()
        ans += l
#    print(i,A[i],l,r,ans)
#print(ans)
ans1 = ans

A.reverse()

left = [0]
right = [0]
ans = 0
for i in range(N):
    l, r = 0, 0
    for j in range(len(left)):
        if A[i] > left[j]:
            buff = i - len(left) + 1 if left[j] == 0 else 1
            l += (A[i] - left[j]) * buff
        else:
            break
    for j in range(len(right)):
        if A[i] > right[j]:
            buff = N-i-1 - len(right) + 1 if right[j] == 0 else 1
            r += (A[i] - right[j]) * buff
        else:
            break
    if r > l:
        right.append(A[i])
        right.sort()
        ans += r
    else:
        left.append(A[i])
        left.sort()
        ans += l
#    print(i,A[i],l,r,ans)
print(max(ans, ans1))