from bisect import*

class BTreeNode:

    def __init__(self):self.key,self.child=[],[]

class BTree:

    def __init__(self):self.root=BTreeNode()

    def search_higher(self,key):

        ptr=self.root

        ret=None

        while ptr.child:

            i=bisect(ptr.key,key)

            if i!=len(ptr.key):ret=ptr.key[i]

            ptr=ptr.child[i]

        i=bisect(ptr.key,key)

        if i!=len(ptr.key):ret=ptr.key[i]

        return ret

    def search_lower(self,key):

        ptr=self.root

        ret=None

        while ptr.child:

            i=bisect_left(ptr.key,key)

            if i:ret=ptr.key[i-1]

            ptr=ptr.child[i]

        i=bisect_left(ptr.key,key)

        if i:ret=ptr.key[i-1]

        return ret

    def insert(self,key):

        def insert_rec(ptr):

            b_size=256

            if not ptr.child:

                insort(ptr.key,key)

                if len(ptr.key)==b_size*2-1:

                    ret=BTreeNode()

                    ret.key=ptr.key[:b_size]

                    ptr.key=ptr.key[b_size:]

                    return ret

            else:

                i=bisect(ptr.key,key)

                tmp=insert_rec(ptr.child[i])

                if tmp:

                    ptr.key.insert(i,tmp.key.pop())

                    ptr.child.insert(i,tmp)

                    if len(ptr.child)==b_size*2:

                        ret=BTreeNode()

                        ret.child=ptr.child[:b_size]

                        ptr.child=ptr.child[b_size:]

                        ret.key=ptr.key[:b_size]

                        ptr.key=ptr.key[b_size:]

                        return ret

        tmp=insert_rec(self.root)

        if tmp:

            root=BTreeNode()

            root.key=[tmp.key.pop()]

            root.child=[tmp,self.root]

            self.root=root

def main():

    n,*a=list(map(int,open(0).read().split()))

    l=[0]*n

    for i,v in enumerate(a,1):l[v-1]=i

    t=BTree()

    insert,search_higher,search_lower=t.insert,t.search_higher,t.search_lower

    insert(0)

    insert(n+1)

    c=0

    for i,v in enumerate(l,1):

        c+=(search_higher(v)-v)*(v-search_lower(v))*i

        insert(v)

    print(c)

main()
from bisect import*

class SqrtSet:

    def __init__(self,block_limit=201):

        self.key=[]

        self.child=[[]]

        self.block_limit=block_limit

    def search_lower(self,key):

        if not key:return None

        ret=None

        i=bisect_left(self.key,key)

        if i:ret=self.key[i-1]

        block=self.child[i]

        i=bisect_left(block,key)

        if i:ret=block[i-1]

        return ret

    def search_higher(self,key):

        if not key:return None

        ret=None

        i=bisect(self.key,key)

        if i<len(self.key):ret=self.key[i]

        block=self.child[i]

        i=bisect(block,key)

        if i<len(block):ret=block[i]

        return ret

    def insert(self,key):

        i=bisect(self.key,key)

        block=self.child[i]

        insort(block,key)

        if len(block)==self.block_limit:

            sep=self.block_limit//2

            self.key.insert(i,block[sep])

            self.child.insert(i+1,block[sep+1:])

            self.child[i]=block[:sep]

def main():

    n,*a=list(map(int,open(0).read().split()))

    l=[0]*n

    for i,v in enumerate(a,1):l[v-1]=i

    t=SqrtSet()

    t.insert(0)

    t.insert(n+1)

    c=0

    for i,v in enumerate(l,1):

        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i

        t.insert(v)

    print(c)

main()
from bisect import *


class BTreeNode:
    def __init__(self):
        self.key, self.child = [], []


class BTree:
    def __init__(self):
        self.root = BTreeNode()

    def search_higher(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect(ptr.key, key)
            if i != len(ptr.key):
                ret = ptr.key[i]
            ptr = ptr.child[i]
        i = bisect(ptr.key, key)
        if i != len(ptr.key):
            ret = ptr.key[i]
        return ret

    def search_lower(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect_left(ptr.key, key)
            if i:
                ret = ptr.key[i - 1]
            ptr = ptr.child[i]
        i = bisect_left(ptr.key, key)
        if i:
            ret = ptr.key[i - 1]
        return ret

    def insert(self, key):
        def insert_rec(ptr):
            b_size = 256
            if not ptr.child:
                insort(ptr.key, key)
                if len(ptr.key) == b_size * 2 - 1:
                    ret = BTreeNode()
                    ret.key = ptr.key[:b_size]
                    ptr.key = ptr.key[b_size:]
                    return ret
            else:
                i = bisect(ptr.key, key)
                tmp = insert_rec(ptr.child[i])
                if tmp:
                    ptr.key.insert(i, tmp.key.pop())
                    ptr.child.insert(i, tmp)
                    if len(ptr.child) == b_size * 2:
                        ret = BTreeNode()
                        ret.child = ptr.child[:b_size]
                        ptr.child = ptr.child[b_size:]
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret

        tmp = insert_rec(self.root)
        if tmp:
            root = BTreeNode()
            root.key = [tmp.key.pop()]
            root.child = [tmp, self.root]
            self.root = root


def main():
    n, *a = list(map(int, open(0).read().split()))
    l = [0] * n
    for i, v in enumerate(a, 1):
        l[v - 1] = i
    t = BTree()
    insert, search_higher, search_lower = t.insert, t.search_higher, t.search_lower
    insert(0)
    insert(n + 1)
    c = 0
    for i, v in enumerate(l, 1):
        c += (search_higher(v) - v) * (v - search_lower(v)) * i
        insert(v)
    print(c)


main()

from bisect import *


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if not key:
            return None
        ret = None
        i = bisect_left(self.key, key)
        if i:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect_left(block, key)
        if i:
            ret = block[i - 1]
        return ret

    def search_higher(self, key):
        if not key:
            return None
        ret = None
        i = bisect(self.key, key)
        if i < len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect(block, key)
        if i < len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect(self.key, key)
        block = self.child[i]
        insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1 :])
            self.child[i] = block[:sep]


def main():
    n, *a = list(map(int, open(0).read().split()))
    l = [0] * n
    for i, v in enumerate(a, 1):
        l[v - 1] = i
    t = SqrtSet()
    t.insert(0)
    t.insert(n + 1)
    c = 0
    for i, v in enumerate(l, 1):
        c += (t.search_higher(v) - v) * (v - t.search_lower(v)) * i
        t.insert(v)
    print(c)


main()

-class BTreeNode: -    def __init__(self): -        self.key, self.child = [], [] +class SqrtSet: +    def __init__(self, block_limit=201): +        self.key = [] +        self.child = [[]] +        self.block_limit = block_limit - -class BTree: -    def __init__(self): -        self.root = BTreeNode() +    def search_lower(self, key): +        if not key: +            return None +        ret = None +        i = bisect_left(self.key, key) +        if i: +            ret = self.key[i - 1] +        block = self.child[i] +        i = bisect_left(block, key) +        if i: +            ret = block[i - 1] +        return ret -        ptr = self.root +        if not key: +            return None -        while ptr.child: -            i = bisect(ptr.key, key) -            if i != len(ptr.key): -                ret = ptr.key[i] -            ptr = ptr.child[i] -        i = bisect(ptr.key, key) -        if i != len(ptr.key): -            ret = ptr.key[i] -        return ret - -    def search_lower(self, key): -        ptr = self.root -        ret = None -        while ptr.child: -            i = bisect_left(ptr.key, key) -            if i: -                ret = ptr.key[i - 1] -            ptr = ptr.child[i] -        i = bisect_left(ptr.key, key) -        if i: -            ret = ptr.key[i - 1] +        i = bisect(self.key, key) +        if i < len(self.key): +            ret = self.key[i] +        block = self.child[i] +        i = bisect(block, key) +        if i < len(block): +            ret = block[i] -        def insert_rec(ptr): -            b_size = 256 -            if not ptr.child: -                insort(ptr.key, key) -                if len(ptr.key) == b_size * 2 - 1: -                    ret = BTreeNode() -                    ret.key = ptr.key[:b_size] -                    ptr.key = ptr.key[b_size:] -                    return ret -            else: -                i = bisect(ptr.key, key) -                tmp = insert_rec(ptr.child[i]) -                if tmp: -                    ptr.key.insert(i, tmp.key.pop()) -                    ptr.child.insert(i, tmp) -                    if len(ptr.child) == b_size * 2: -                        ret = BTreeNode() -                        ret.child = ptr.child[:b_size] -                        ptr.child = ptr.child[b_size:] -                        ret.key = ptr.key[:b_size] -                        ptr.key = ptr.key[b_size:] -                        return ret - -        tmp = insert_rec(self.root) -        if tmp: -            root = BTreeNode() -            root.key = [tmp.key.pop()] -            root.child = [tmp, self.root] -            self.root = root +        i = bisect(self.key, key) +        block = self.child[i] +        insort(block, key) +        if len(block) == self.block_limit: +            sep = self.block_limit // 2 +            self.key.insert(i, block[sep]) +            self.child.insert(i + 1, block[sep + 1 :]) +            self.child[i] = block[:sep] -    t = BTree() -    insert, search_higher, search_lower = t.insert, t.search_higher, t.search_lower -    insert(0) -    insert(n + 1) +    t = SqrtSet() +    t.insert(0) +    t.insert(n + 1) -        c += (search_higher(v) - v) * (v - search_lower(v)) * i -        insert(v) +        c += (t.search_higher(v) - v) * (v - t.search_lower(v)) * i +        t.insert(v)