import sys



def main():
    N = int(input())

    A = []
    for i, a in enumerate(map(int, input().split(' '))):
        A.append((a, i))
    A.sort(reverse=True)

    i = 0
    L = 0
    R = N - 1
    S = 0
    while i < len(A):
        a0, p0 = A[i]
        dL = abs(L - p0)
        dR = abs(R - p0)
        if dL < dR:
            if i + 3 <= len(A):
                a1, p1 = A[i + 1]
                a2, p2 = A[i + 2]
                if a1 + a2 > a0 and p1 < p0 and p2 < p0:
                    S += a0 * dL + a1 * abs(R - p1) + a2 * abs(R - 1 - p2)
                    L += 1
                    R -= 2
                    i += 3
                    continue
            S += a0 * dR
            R -= 1
        else:
            if i + 3 <= len(A):
                a1, p1 = A[i + 1]
                a2, p2 = A[i + 2]
                if a1 + a2 > a0 and p1 > p0 and p2 > p0:
                    S += a0 * dL + a1 * abs(L - p1) + a2 * abs(L + 1 - p2)
                    L += 2
                    R -= 1
                    i += 3
                    continue
            S += a0 * dL
            L += 1
        i += 1
    print(S)


if __name__ == '__main__':
    main()
