import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))

B = [[A[i], i] for i in range(n)]
B.sort(reverse=True)

# S = [A[0]]
# for i in range(1, n):
#     S.append(A[i] + S[-1])
l = 0
r = n-1
ans = 0
for i in range(n):
    ind = B[i][1]
    # print(ind)
    if r > ind and B[i][0] * ((r-ind) - (ind-l)) + sum(A[(ind+1):]) - sum(A[:ind]) >= 0:
        # print(ind,"r")
        ans += B[i][0] * ((r-ind))
        r -= 1
        A[ind] = 0
    else:
        ans += B[i][0] * ((ind-l))
        # print(ind,"l")
        l += 1
        A[ind] = 0
print(ans)
