import numpy as np
import sys
input = sys.stdin.readline
from collections import deque

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

values = []
num_indcies = {}
for i, a in enumerate(A):
    if not a in num_indcies:
        num_indcies[a] = [i]
        values.append(a)
    else:
        num_indcies[a].append(i)

values = sorted(values, reverse=True)
ans = 0
L = 0
R = N-1

ans = 0
for i, val in enumerate(values):
    indices = deque(num_indcies[val])
    print(i, val, ans, L , R)
    while len(indices) > 1:
        if abs(R - indices[0]) < abs(indices[-1] - L):
            ans += val *  abs(indices[-1]-L)
            indices.pop()
            L += 1
        else:
            ans += val *  abs(R-indices[0])
            indices.popleft()
            R -= 1
        print("indices", indices)
        print("内部", i, val, ans, L , R)
    if abs(R - indices[0]) < abs(indices[-1] - L):
        ans += val *  abs(indices[-1]-L)
        indices.pop()
        L += 1
    elif abs(R - indices[0]) > abs(indices[-1] - L):
        ans += val *  abs(R-indices[0])
        indices.popleft()
        R -= 1
    else:
        ans += val *  abs(indices[-1]-L)
        if i == len(values) -1:
            continue
        _indices = deque(num_indcies[values[i+1]])
        if abs(R - _indices[0]) < abs(_indices[-1] - L):
            L += 1
        else:
            R -= 1

print(ans)

    