class BIT_index:

    def __init__(self, n):

        self.BIT_prev = [n] * (n + 1)

        self.BIT_next = [n] * (n + 1)

        self.n = n



    def __addElement(self, BIT, idx):

        value = idx

        idx += 1

        while idx > 0:

            BIT[idx] = min(BIT[idx], value)

            idx -= idx & -idx



    def addElement(self, idx):

        self.__addElement(self.BIT_prev, self.n - 1 - idx)

        self.__addElement(self.BIT_next, idx)



    def __getIndex(self, BIT, idx):

        idx += 1

        ans = self.n

        while idx <= self.n:

            ans = min(ans, BIT[idx])

            idx += idx & -idx

        return ans



    def getIndexPrev(self, idx):

        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)



    def getIndexNext(self, idx):

        return self.__getIndex(self.BIT_next, idx)





N = int(eval(input()))

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



Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]



BIT = BIT_index(N)

ans = 0

for i, B in enumerate(Bs):

    iN = BIT.getIndexNext(B)

    iP = BIT.getIndexPrev(B)

    BIT.addElement(B)

    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))



print(ans)

N = int(eval(input()))

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



iAs = [0] * (N + 1)

for i, A in enumerate(As):

    iAs[A] = i



ans = 0

iLs = list(range(N + 1))

iRs = list(range(N + 1))

for A in reversed(list(range(1, N + 1))):

    iA = iAs[A]

    iL, iR = iLs[iA], iRs[iA]

    ans += A * (iA - iL + 1) * (iR - iA + 1)

    iLs[iR + 1] = iL

    iRs[iL - 1] = iR



print(ans)

class BIT_index:
    def __init__(self, n):
        self.BIT_prev = [n] * (n + 1)
        self.BIT_next = [n] * (n + 1)
        self.n = n

    def __addElement(self, BIT, idx):
        value = idx
        idx += 1
        while idx > 0:
            BIT[idx] = min(BIT[idx], value)
            idx -= idx & -idx

    def addElement(self, idx):
        self.__addElement(self.BIT_prev, self.n - 1 - idx)
        self.__addElement(self.BIT_next, idx)

    def __getIndex(self, BIT, idx):
        idx += 1
        ans = self.n
        while idx <= self.n:
            ans = min(ans, BIT[idx])
            idx += idx & -idx
        return ans

    def getIndexPrev(self, idx):
        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)

    def getIndexNext(self, idx):
        return self.__getIndex(self.BIT_next, idx)


N = int(eval(input()))
As = list(map(int, input().split()))
Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]
BIT = BIT_index(N)
ans = 0
for i, B in enumerate(Bs):
    iN = BIT.getIndexNext(B)
    iP = BIT.getIndexPrev(B)
    BIT.addElement(B)
    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))
print(ans)

N = int(eval(input()))
As = list(map(int, input().split()))
iAs = [0] * (N + 1)
for i, A in enumerate(As):
    iAs[A] = i
ans = 0
iLs = list(range(N + 1))
iRs = list(range(N + 1))
for A in reversed(list(range(1, N + 1))):
    iA = iAs[A]
    iL, iR = iLs[iA], iRs[iA]
    ans += A * (iA - iL + 1) * (iR - iA + 1)
    iLs[iR + 1] = iL
    iRs[iL - 1] = iR
print(ans)

-class BIT_index: -    def __init__(self, n): -        self.BIT_prev = [n] * (n + 1) -        self.BIT_next = [n] * (n + 1) -        self.n = n - -    def __addElement(self, BIT, idx): -        value = idx -        idx += 1 -        while idx > 0: -            BIT[idx] = min(BIT[idx], value) -            idx -= idx & -idx - -    def addElement(self, idx): -        self.__addElement(self.BIT_prev, self.n - 1 - idx) -        self.__addElement(self.BIT_next, idx) - -    def __getIndex(self, BIT, idx): -        idx += 1 -        ans = self.n -        while idx <= self.n: -            ans = min(ans, BIT[idx]) -            idx += idx & -idx -        return ans - -    def getIndexPrev(self, idx): -        return self.__getIndex(self.BIT_prev, self.n - 1 - idx) - -    def getIndexNext(self, idx): -        return self.__getIndex(self.BIT_next, idx) - - -Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])] -BIT = BIT_index(N) +iAs = [0] * (N + 1) +for i, A in enumerate(As): +    iAs[A] = i -for i, B in enumerate(Bs): -    iN = BIT.getIndexNext(B) -    iP = BIT.getIndexPrev(B) -    BIT.addElement(B) -    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP)) +iLs = list(range(N + 1)) +iRs = list(range(N + 1)) +for A in reversed(list(range(1, N + 1))): +    iA = iAs[A] +    iL, iR = iLs[iA], iRs[iA] +    ans += A * (iA - iL + 1) * (iR - iA + 1) +    iLs[iR + 1] = iL +    iRs[iL - 1] = iR