#!/bin/python

import sys


def maxsums(B):
    C=[]
    for k in xrange(0,len(B)):
        for i in xrange(0,len(B)-k):
                j=i+k
                C.append(max(B[i:(j+1)]))
    return C

def maxs(B):
    return maxsums(maxsums(B))

def t(n,a,b):
    mx=max(a,b)
    mn=min(a,b)
    a=mn
    b=mx
    r=0
    s=0
    for i in xrange(0,b+1):
        s+=n+r
        #print s
        if r<a:
            r+=1
    g=a+n
    while g>0:
        g-=1
        s+=g
        #print s
    return s

def walk_(V,start,l,val,dr):
    if dr==1:
        for i in xrange(start,l):
            if V[i]>val:
                return V[start:i]
        return V[start:l]
    else:
        l=-1
        for i in xrange(start,0,-1):
            if V[i]>=val:
                return V[i+1:start+1]
            l=i
        if l==-1:
            return V[0:0]
        else:
            return V[0:start+1]


def walk_s(V,start,l,val,dr):
    if dr==1:
        for i in xrange(start,l):
            if V[i]>=val:
                return V[start:i]
        return V[start:l]
    else:
        l=-1
        for i in xrange(start,0,-1):
            if V[i]>=val:
                return V[i+1:start+1]
            l=i
        if l==-1:
            return V[0:0]
        else:
            return V[0:start+1]

def walk(V,val,dr):
    if dr==1:
        i=0
        while(V[i]<val and i<len(V)):
            i+=1
        return V[0:i]
    else:
        i=len(V)-1
        l=i
        while(V[i]<=val and i>=0):
            i-=1
        return V[i+1:l+1]

def tmax(V,n):
    v=V[n]
    o=0
    oo=0
    for i in xrange(n+1,len(V)):
            if V[i]!=v:
                break
            else:
                o+=1
            ii=i
    
    for i in xrange(n-1,0,-1):
            if V[i]!=v:
                break
            else:
                oo+=1
            jj=i
    p1=n-oo
    p2=len(V)-n-1-o
    s=0
    k=o+oo+1
    r=p1
    i=k
    l=1
    m=max(p1,p2)
    mn=min(p1,p2)
    while(l<=m):
        if p1+p2>0 :
            if p1>=1:
                s+=t(i,r,p2+p1-1)
                r=r+i+p1+p2-1
            else:
                s+=t(i,r,p2+p1)
                r=r+i+p2
        else:
            s+=t(i,r,0)
            r=r+i
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        if i<k+mn:
            i+=1
        l+=1
    k=i
    while(k>0):
        if p1+p2>0:
            if p1>=1:
                s+=t(k,r,p2+p1-1)
                r=r+k+p1+p2-1
            else:
                s+=t(k,r,p2+p1)
                r=r+k+p2
        else:
            s+=t(k,r,0)
            r=r+k
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        k-=1
    return s

def slice(V,n,v):
    o=0
    if n==1:
        for i in xrange(0,len(V)):
            if V[i]!=v:
                break
            else:
                o+=1
    else:
        for i in xrange(len(V)-1,0,-1):
            if V[i]!=v:
                break
            else:
                o+=1
    return o

def t_1_(n,suffix,a,b):
    p1=a
    p2=b
    s=0
    k=n
    r=p2+suffix
    i=k
    l=1
    m=max(p1,p2)
    mn=min(p1,p2)
    while(l<=m):
        s+=t(i,p1,r)
        if p1!=0:
            p1-=1
        if r!=0:
            r-=1
        if i<k+mn:
            i+=1
        l+=1
    k=i
    while(k>0):
        s+=t(k,0,0)
        k-=1
    return s


def t_1(n,suffix,a,b):
    p1=a
    p2=b
    s=0
    k=n
    r=p2
    i=k
    l=1
    m=max(p1,p2)
    mn=min(p1,p2) #p1-1+prefix if p1>0 else prefix
    while(l<=m):
        if suffix!=0:
            suffix-=1
        r=p2+suffix
        s+=t(i,p1,r)
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        if i<k+mn:
            i+=1
        l+=1
    k=i
    while(k>0):
        if suffix!=0:
            suffix-=1
        r=p2+suffix
        s+=t(k,p1,r)
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        k-=1
    return s

def t_0(n,a,b,prefix):
    p1=a
    p2=b
    s=0
    k=n
    r=p1
    i=k
    l=1
    m=max(p1,p2)
    mn=min(p1,p2) #p1-1+prefix if p1>0 else prefix
    while(l<=m):
        if l>=2:
            r=p1+prefix
        s+=t(i,r,p2)
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        if prefix!=0 and l>=2:
            prefix-=1
        if i<k+mn:
            i+=1
        l+=1
    k=i
    while(k>0):
        r=p1+prefix
        s+=t(k,r,p2)
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        if prefix!=0:
            prefix-=1
        k-=1
    return s

def t_(n,a,b):
    p1=a
    p2=b
    s=0
    k=n
    r=p1
    i=k
    l=1
    m=max(p1,p2)
    mn=min(p1,p2)
    while(l<=m):
        s+=t(i,p1,p2)
        if p1!=0:
            p1-=1
        if p2!=0:
            p2-=1
        if i<k+mn:
            i+=1
        l+=1
    k=i
    while(k>0):
        s+=t(k,0,0)
        k-=1
    return s

def tt(a,b,c,d,V,v,o_,n):
    if a==0 and d==0:
        if c==0 or b==0:
            if c==0:
                o=slice(V[0],-1,v)
                o_.extend(range(n-o,n))
                return t_(o+1,len(V[0])-o,0)
            else:
                o=slice(V[0],1,v)
                o_.extend(range(n+1,n+o+1))
                return t_(o+1,0,len(V[0])-o)
        else:
            o=slice(V[0],-1,v)
            oo=slice(V[1],1,v)
            o_.extend(range(n-o,n+oo+1))
            return t_(o+oo+1,len(V[0])-o,len(V[1])-oo)
    elif a!=0:
        if c==0 or b==0:
            if c==0:
                o=slice(V[1],-1,v)
                o_.extend(range(n-o,n))
                return t_0(o+1,len(V[1])-o,0,len(V[0]))
            else:
                o=slice(V[1],1,v)
                o_.extend(range(n+1,n+o+1))
                return t_0(o+1,0,len(V[1])-o,len(V[0]))
        else:
            o=slice(V[1],-1,v)
            oo=slice(V[2],1,v)
            o_.extend(range(n-o,n+oo+1))
            return t_0(o+oo+1,len(V[1])-o,len(V[2])-oo,len(V[0]))
    else:
        if c==0 or b==0:
            if c==0:
                o=slice(V[0],-1,v)
                o_.extend(range(n-o,n))
                return t_1(o+1,len(V[1]),len(V[0])-o,0)
            else:
                o=slice(V[0],1,v)
                o_.extend(range(n+1,n+o+1))
                return t_1(o+1,len(V[1]),0,len(V[0])-o)
        else:
            o=slice(V[0],-1,v)
            oo=slice(V[1],1,v)
            o_.extend(range(n-o,n+oo+1))
            return t_1(o+oo+1,len(V[2]),len(V[0])-o,len(V[1])-oo)

def segment(V,n,l,o):
    if n in o:
        return V[n]*segment(V,n+1,l,o)
    if(n==0):
        part11=walk_(V,n+1,l,V[n],1)
        part00=walk(V,V[n],-1)
        if len(part11)==l-1:
            return V[n]*tmax(V,0)+segment(V,1,l,o)
        elif len(part11)!=0:
            if len(part00)!=0:
                return V[n]*tt(1,0,1,0,[(part00),(part11)],V[n],o,n)+segment(V,1,l,o)
            else:
                return V[n]*tt(0,0,1,0,[(part11)],V[n],o,n)+segment(V,1,l,o)
        else:
            #if len(part00)!=0:
            #    return [tt(1,0,0,0,[(part00)],V[n]),segment(V,1,l)]
            #else:
            return V[n]*1+segment(V,1,l,o)
    elif (n==l-1):
        part01=walk_(V,n-1,l,V[n],-1)
        part10=walk(V,V[n],1)
        if len(part01)==l-1:
            return V[n]*tmax(V,l-1)
        elif len(part01)!=0:
            if len(part10)!=0:
                return V[n]*tt(0,1,0,1,[(part01),(part10)],V[n],o,n)
            else:
                return V[n]*tt(0,1,0,0,[(part01)],V[n],o,n)
        else:
            if len(part10)!=0:
                return V[n]*tt(0,0,0,1,[(part10)],V[n],o,n)
            else:
                return 1
    else:
        part11=walk_(V,n+1,l,V[n],1)
        part01=walk_(V,n-1,l,V[n],-1)
        if len(part11)+len(part01)==l-1:
            return V[n]*tmax(V,n)+segment(V,n+1,l,o)
        elif len(part11)==l-n-1:
            part10=walk(V,V[n],1)
            if len(part10)!=0:
                return V[n]*tt(0,1,1,1,[(part01),(part11),(part10)],V[n],o,n)+segment(V,n+1,l,o)
            else:
                return V[n]*tt(0,1,1,0,[(part01),(part11)],V[n],o,n)+segment(V,n+1,l,o)
        elif len(part01)==l-n-1:
            part00=walk(V,V[n],-1)
            if len(part00)!=0:
                return V[n]*tt(1,1,1,0,[(part00),(part01),(part11)],V[n],o,n)+segment(V,n+1,l,o)
            else:
                return V[n]*tt(0,1,1,0,[(part01),(part11)],V[n],o,n)+segment(V,n+1,l,o)
        elif len(part11)!=0 and len(part01)==0:
            return V[n]*tt(0,0,1,0,[(part11)],V[n],o,n)+segment(V,n+1,l,o)
        elif len(part01)!=0:
            return V[n]*tt(0,1,0,0,[(part01)],V[n],o,n)+segment(V,n+1,l,o)
        else:
            return V[n]+segment(V,n+1,l,o)


if __name__ == "__main__":
    n = int(raw_input().strip())
    A = map(int, raw_input().strip().split(' '))
    result = segment(list(A),0,n,[])
    print result