n=int(eval(input()))

a=list(map(int,input().split()))

a=sorted(list(enumerate(a)),key=lambda x:x[1])



l=1

while l<2*(n+2)-1:

	l*=2

l-=1

seg=[True]*l

seg[0]=False



def update(i):

	if seg[i]:

		seg[i]=False

		update((i-1)//2)



update((l-1)//2)

update((l-1)//2+n+1)



def search_left(i,j):

	if j==1:

		if i%2==1:

			return search_left((i-1)//2,1)

		else:

			if seg[i-1]:

				return search_left((i-1)//2,1)

			else:

				return search_left(i-1,0)

	else:

		if i<l//2:

			return search_left(2*i+2-seg[2*i+2],0)

		else:

			return i



def search_right(i,j):

	if j==1:

		if i%2==0:

			return search_right((i-1)//2,1)

		else:

			if seg[i+1]:

				return search_right((i-1)//2,1)

			else:

				return search_right(i+1,0)

	else:

		if i<l//2:

			return search_right(2*i+1+seg[2*i+1],0)

		else:

			return i



ans=0

for i,j in a:

	s=(l//2+1+i)

	p=search_left(s,1)

	q=search_right(s,1)

	ans+=(s-p)*(q-s)*j

	update(s)



print(ans)
def main():

    n = int(eval(input()))

    a = list(map(int, input().split()))

    a = sorted(list(enumerate(a)), key=lambda x: -x[1])



    class unionfind():

        # size:要素数,tree：unionfind木

        def __init__(self, size):  # self,要素数

            self.size = size

            self.tree = [i for i in range(self.size)]  # root,depth



        # rootを探す

        def root(self, index):

            temp_list = []

            temp = self.tree[index]

            while index != temp:

                temp_list.append(index)

                index = temp

                temp = self.tree[index]

            for i in temp_list:

                self.tree[i] = index

            return index



        # 結合

        def unite_r(self, index1, index2):

            r1 = self.root(index1)

            r2 = self.root(index2)

            if r1 < r2:

                self.tree[r1] = r2

            else:

                self.tree[r2] = r1



        def unite_l(self, index1, index2):

            r1 = self.root(index1)

            r2 = self.root(index2)

            if r1 > r2:

                self.tree[r1] = r2

            else:

                self.tree[r2] = r1



        # 同じか判定

        def same(self, index1, index2):

            r1 = self.root(index1)

            r2 = self.root(index2)

            return r1 == r2



    ur = unionfind(n+2)

    ul = unionfind(n+2)

    vis = [False]*(n+2)

    ans = 0

    for i, j in a:

        vis[i+1] = True

        if vis[i+2]:

            ur.unite_r(i+1, i+2)

            ul.unite_l(i+1, i+2)

        if vis[i]:

            ur.unite_r(i, i+1)

            ul.unite_l(i, i+1)

        ans += j*(ur.root(i+1)-i)*(i+2-ul.root(i+1))

    print(ans)





main()

n = int(eval(input()))
a = list(map(int, input().split()))
a = sorted(list(enumerate(a)), key=lambda x: x[1])
l = 1
while l < 2 * (n + 2) - 1:
    l *= 2
l -= 1
seg = [True] * l
seg[0] = False


def update(i):
    if seg[i]:
        seg[i] = False
        update((i - 1) // 2)


update((l - 1) // 2)
update((l - 1) // 2 + n + 1)


def search_left(i, j):
    if j == 1:
        if i % 2 == 1:
            return search_left((i - 1) // 2, 1)
        else:
            if seg[i - 1]:
                return search_left((i - 1) // 2, 1)
            else:
                return search_left(i - 1, 0)
    else:
        if i < l // 2:
            return search_left(2 * i + 2 - seg[2 * i + 2], 0)
        else:
            return i


def search_right(i, j):
    if j == 1:
        if i % 2 == 0:
            return search_right((i - 1) // 2, 1)
        else:
            if seg[i + 1]:
                return search_right((i - 1) // 2, 1)
            else:
                return search_right(i + 1, 0)
    else:
        if i < l // 2:
            return search_right(2 * i + 1 + seg[2 * i + 1], 0)
        else:
            return i


ans = 0
for i, j in a:
    s = l // 2 + 1 + i
    p = search_left(s, 1)
    q = search_right(s, 1)
    ans += (s - p) * (q - s) * j
    update(s)
print(ans)

def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a = sorted(list(enumerate(a)), key=lambda x: -x[1])

    class unionfind:
        # size:要素数,tree：unionfind木
        def __init__(self, size):  # self,要素数
            self.size = size
            self.tree = [i for i in range(self.size)]  # root,depth

        # rootを探す
        def root(self, index):
            temp_list = []
            temp = self.tree[index]
            while index != temp:
                temp_list.append(index)
                index = temp
                temp = self.tree[index]
            for i in temp_list:
                self.tree[i] = index
            return index

        # 結合
        def unite_r(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 < r2:
                self.tree[r1] = r2
            else:
                self.tree[r2] = r1

        def unite_l(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 > r2:
                self.tree[r1] = r2
            else:
                self.tree[r2] = r1

        # 同じか判定
        def same(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            return r1 == r2

    ur = unionfind(n + 2)
    ul = unionfind(n + 2)
    vis = [False] * (n + 2)
    ans = 0
    for i, j in a:
        vis[i + 1] = True
        if vis[i + 2]:
            ur.unite_r(i + 1, i + 2)
            ul.unite_l(i + 1, i + 2)
        if vis[i]:
            ur.unite_r(i, i + 1)
            ul.unite_l(i, i + 1)
        ans += j * (ur.root(i + 1) - i) * (i + 2 - ul.root(i + 1))
    print(ans)


main()

-n = int(eval(input())) -a = list(map(int, input().split())) -a = sorted(list(enumerate(a)), key=lambda x: x[1]) -l = 1 -while l < 2 * (n + 2) - 1: -    l *= 2 -l -= 1 -seg = [True] * l -seg[0] = False +def main(): +    n = int(eval(input())) +    a = list(map(int, input().split())) +    a = sorted(list(enumerate(a)), key=lambda x: -x[1]) + +    class unionfind: +        # size:要素数,tree：unionfind木 +        def __init__(self, size):  # self,要素数 +            self.size = size +            self.tree = [i for i in range(self.size)]  # root,depth + +        # rootを探す +        def root(self, index): +            temp_list = [] +            temp = self.tree[index] +            while index != temp: +                temp_list.append(index) +                index = temp +                temp = self.tree[index] +            for i in temp_list: +                self.tree[i] = index +            return index + +        # 結合 +        def unite_r(self, index1, index2): +            r1 = self.root(index1) +            r2 = self.root(index2) +            if r1 < r2: +                self.tree[r1] = r2 +            else: +                self.tree[r2] = r1 + +        def unite_l(self, index1, index2): +            r1 = self.root(index1) +            r2 = self.root(index2) +            if r1 > r2: +                self.tree[r1] = r2 +            else: +                self.tree[r2] = r1 + +        # 同じか判定 +        def same(self, index1, index2): +            r1 = self.root(index1) +            r2 = self.root(index2) +            return r1 == r2 + +    ur = unionfind(n + 2) +    ul = unionfind(n + 2) +    vis = [False] * (n + 2) +    ans = 0 +    for i, j in a: +        vis[i + 1] = True +        if vis[i + 2]: +            ur.unite_r(i + 1, i + 2) +            ul.unite_l(i + 1, i + 2) +        if vis[i]: +            ur.unite_r(i, i + 1) +            ul.unite_l(i, i + 1) +        ans += j * (ur.root(i + 1) - i) * (i + 2 - ul.root(i + 1)) +    print(ans) -def update(i): -    if seg[i]: -        seg[i] = False -        update((i - 1) // 2) - - -update((l - 1) // 2) -update((l - 1) // 2 + n + 1) - - -def search_left(i, j): -    if j == 1: -        if i % 2 == 1: -            return search_left((i - 1) // 2, 1) -        else: -            if seg[i - 1]: -                return search_left((i - 1) // 2, 1) -            else: -                return search_left(i - 1, 0) -    else: -        if i < l // 2: -            return search_left(2 * i + 2 - seg[2 * i + 2], 0) -        else: -            return i - - -def search_right(i, j): -    if j == 1: -        if i % 2 == 0: -            return search_right((i - 1) // 2, 1) -        else: -            if seg[i + 1]: -                return search_right((i - 1) // 2, 1) -            else: -                return search_right(i + 1, 0) -    else: -        if i < l // 2: -            return search_right(2 * i + 1 + seg[2 * i + 1], 0) -        else: -            return i - - -ans = 0 -for i, j in a: -    s = l // 2 + 1 + i -    p = search_left(s, 1) -    q = search_right(s, 1) -    ans += (s - p) * (q - s) * j -    update(s) -print(ans) +main()