import sys
readline = sys.stdin.readline


N = int(readline())
A = list(map(int, readline().split()))

ai = [(a, i) for i,a in enumerate(A)]
ai.sort(reverse=True)
_, indices = zip(*ai)

u = [0, N - 1]


ans = 0
for i in range(N):
    ind = indices[i]
    if u[0] == u[1]:
        t = 0
    else:
        if ind - u[0] < u[1] - ind:
            t = 1
        elif ind - u[0] > u[1] - ind:
            t = 0
        else:
            if indices[i + 1] - u[0] < u[1] - indices[i + 1]:
                t = 0
            else:
                t = 1
    
    ans += A[ind] * abs(u[t] - ind)
    if t == 0:
        u[t] += 1
    else:
        u[t] -= 1

print(ans)

