import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
b = []
r = [0]
for i in range(n):
    b.append((a[i],i))
for i in a:
    r.append(r[-1]+i)

b.sort(reverse=True)

ans = 0

def f(left,right,k,c):
    if k == n:
        return c
    i,j = b[k]
    p = r[j]
    q = r[n]-r[j+1]
    x = (j-left)*i
    y = (right-j)*i
    if x >= 0 and x+p >= y+q:
        return f(left+1, right, k+1, c+x)
    else:
        return f(left, right-1, k+1, c+y)

ans = f(0,n-1,0,0)

print(ans)