n = int(input())
a = list(map(int,input().split()))
right = 0
left = n-1
stay = []
l = []
ans = 0
for i in range(n):
    l.append([a[i],i])
l.sort(reverse=True)
for i in range(n):
    l0 = 0
    r0 = 0
    for j in range(l[i][1]-1):
        r0 = max(r0,a[j])
    for j in range(l[i][1]+1,n):
        l0 = max(l0,a[j])
    r0 = l[i][0] - r0
    l0 = l[i][0] - l0
    #print(l0,r0)
    if len(stay) == 0:
        if (left - l[i][1])*r0 > (l[i][1] - right)*l0:
            ans += l[i][0]*(left - l[i][1])
            left -= 1
        elif (left - l[i][1])*r0 < (l[i][1] - right)*l0:
            ans += l[i][0]*(l[i][1]-right)
            right += 1
        else:
            stay.append(l[i])
        a[l[i][1]] = 0
    else:
        k = len(stay)
        if (left - l[i][1]-k//2)*r0 > (l[i][1] - right - k//2)*l0:
            for j in range(k):
                if j % 2 == 0:
                    ans += (stay[k-1-j][1] - right - k//2+j)*stay[k-1-j][0]
                    right += 1
                else:
                    ans += (left - stay[k-1-j][1]-k//2 + j)*stay[k-1-j][0]
                    left -= 1
            ans += l[i][0]*(left - l[i][1])
            left -= 1
            stay = []
        elif (left - l[i][1] - k//2)*r0 < (l[i][1] - right - k//2)*l0:
            for j in range(k):
                if j % 2 == 1:
                    ans += abs((stay[k-1-j][1] - right - k//2+j)*stay[k-1-j][0])
                    right += 1
                else:
                    ans += abs((left - stay[k-1-j][1]-k//2 + j)*stay[k-1-j][0])
                    left -= 1
            ans += l[i][0]*(l[i][1]-right)
            right += 1
            stay = []
        else:
            stay.append(l[i])
        a[l[i][1]] = 0
    #print(stay,ans)
if len(stay) > 0:
    k = len(stay)
    for j in range(k):
        if j % 2 == 0:
            ans += abs((stay[k-1-j][1] - right - k//2+j)*stay[k-1-j][0])
            right += 1
        else:
            ans += abs((left - stay[k-1-j][1]-k//2 + j)*stay[k-1-j][0])
            left -= 1
print(ans)