import sys

def input():
    return sys.stdin.readline()[:-1] 


class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

def main():

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

    ST = SegmentTree(P,max,-10**27)

    def bisect(i,j,ST,num,index,P,Smin,Smin_rev,left_flag):
        if left_flag:    
            if i==j:
                if P[i]>num:
                    return i
                else:
                    return i-1
            
            if Smin[j+1]==num:
                return -1
            if P[j]>num:
                return j
        else:
            if i==j:
                if P[i]>num:
                    return i
                else:
                    return i+1
            
            if Smin_rev[i-1]==num:
                return N
            if P[i]>num:
                return i

        if not left_flag:
            while j-i>1:
                if ST.get(index+1,(i+j)//2)<num:
                    i = (i+j)//2
                else:
                    j = (i+j)//2
            return j
        else:
            while j-i>1:
                if ST.get((i+j)//2,index-1)<num:
                    j = (i+j)//2
                else:
                    i = (i+j)//2
            return i

    Smin = []
    smin = -10**27
    for i in range(N):
        smin = max(smin,P[i])
        Smin.append(smin)

    Smin_rev = []
    smin = -10**27
    for i in range(N):
        smin = max(smin,P[N-i-1])
        Smin_rev.append(smin)
    Smin_rev = Smin_rev[::-1]


    score = 0

    for i in range(N):
        if i==0:
            right1 = bisect(i+1,N-1,ST,P[i],i,P,Smin,Smin_rev,False)
            if right1>=N-1:
                right2 = N
            else:
                right2 = bisect(right1+1,N-1,ST,P[i],right1,P,Smin,Smin_rev,False)
            right1,right2 = right1-i,right2-i
            left1 = 1
            left2 = 1
            
        elif i==N-1:
            left1 = bisect(0,i-1,ST,P[i],i,P,Smin,Smin_rev,True)
            if left1<=0:
                left2 = -1
            else:
                left2 = bisect(0,left1-1,ST,P[i],left1,P,Smin,Smin_rev,True)
            left1,left2 = i-left1,i-left2
            right1 = 1
            right2 = 1
        else:
            right1 = bisect(i+1,N-1,ST,P[i],i,P,Smin,Smin_rev,False)
            if right1>=N-1:
                right2 = N
            else:
                right2 = bisect(right1+1,N-1,ST,P[i],right1,P,Smin,Smin_rev,False)
            right1,right2 = right1-i,right2-i

            left1 = bisect(0,i-1,ST,P[i],i,P,Smin,Smin_rev,True)
            if left1<=0:
                left2 = -1
            else:
                left2 = bisect(0,left1-1,ST,P[i],left1,P,Smin,Smin_rev,True)
            left1,left2 = i-left1,i-left2
        
        score += (left1*(right2-right1) + (left2-left1)*right1)*P[i]
    print(score)

main()    

### FIXED CODE ###

N =int(input())

print(N**3)