n = int(eval(input()))

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



P = [0]*n

for i, a in enumerate(A):

    P[a-1] = i



import heapq

q = []

heapq.heapify(q)

R = [n-1]*n

for i, a in enumerate(A):

    while q and q[0]*(-1) > a:

        v = heapq.heappop(q)*(-1)

        R[v-1] = i-1

    heapq.heappush(q, a*(-1))



q = []

L = [0]*n

for j in range(n):

    i = n-1-j

    a = A[i]

    while q and q[0]*(-1) > a:

        v = heapq.heappop(q)*(-1)

        L[v-1] = i+1

    heapq.heappush(q, a*(-1))



#print(L)

#print(R)

ans = 0

for i in range(n):

    a = i+1

    l, r, p = L[i], R[i], P[i]

    ans += (p-l+1)*(r-p+1)*a

print(ans)
n = int(eval(input()))

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

A = [a-1 for a in A]



P = [-1]*n

for i, a in enumerate(A):

    P[a] = i



R = [n]*n

q = []

import heapq

heapq.heapify(q)

for i in range(n):

    while q:

        if -q[0] > A[i]:

            v = -heapq.heappop(q)

            R[v] = i

        else:

            break

    heapq.heappush(q, -A[i])



L = [-1]*n

q = []

heapq.heapify(q)

for i in reversed(list(range(n))):

    while q:

        if -q[0] > A[i]:

            v = -heapq.heappop(q)

            L[v] = i

        else:

            break

    heapq.heappush(q, -A[i])

#print(P)

#print(R)

#print(L)

ans = 0

for i in range(n):

    ans += (P[i]-L[i])*(R[i]-P[i])*(i+1)

print(ans)

n = int(eval(input()))
A = list(map(int, input().split()))
P = [0] * n
for i, a in enumerate(A):
    P[a - 1] = i
import heapq

q = []
heapq.heapify(q)
R = [n - 1] * n
for i, a in enumerate(A):
    while q and q[0] * (-1) > a:
        v = heapq.heappop(q) * (-1)
        R[v - 1] = i - 1
    heapq.heappush(q, a * (-1))
q = []
L = [0] * n
for j in range(n):
    i = n - 1 - j
    a = A[i]
    while q and q[0] * (-1) > a:
        v = heapq.heappop(q) * (-1)
        L[v - 1] = i + 1
    heapq.heappush(q, a * (-1))
# print(L)
# print(R)
ans = 0
for i in range(n):
    a = i + 1
    l, r, p = L[i], R[i], P[i]
    ans += (p - l + 1) * (r - p + 1) * a
print(ans)

n = int(eval(input()))
A = list(map(int, input().split()))
A = [a - 1 for a in A]
P = [-1] * n
for i, a in enumerate(A):
    P[a] = i
R = [n] * n
q = []
import heapq

heapq.heapify(q)
for i in range(n):
    while q:
        if -q[0] > A[i]:
            v = -heapq.heappop(q)
            R[v] = i
        else:
            break
    heapq.heappush(q, -A[i])
L = [-1] * n
q = []
heapq.heapify(q)
for i in reversed(list(range(n))):
    while q:
        if -q[0] > A[i]:
            v = -heapq.heappop(q)
            L[v] = i
        else:
            break
    heapq.heappush(q, -A[i])
# print(P)
# print(R)
# print(L)
ans = 0
for i in range(n):
    ans += (P[i] - L[i]) * (R[i] - P[i]) * (i + 1)
print(ans)

-P = [0] * n +A = [a - 1 for a in A] +P = [-1] * n -    P[a - 1] = i +    P[a] = i +R = [n] * n +q = [] +heapq.heapify(q) +for i in range(n): +    while q: +        if -q[0] > A[i]: +            v = -heapq.heappop(q) +            R[v] = i +        else: +            break +    heapq.heappush(q, -A[i]) +L = [-1] * n -R = [n - 1] * n -for i, a in enumerate(A): -    while q and q[0] * (-1) > a: -        v = heapq.heappop(q) * (-1) -        R[v - 1] = i - 1 -    heapq.heappush(q, a * (-1)) -q = [] -L = [0] * n -for j in range(n): -    i = n - 1 - j -    a = A[i] -    while q and q[0] * (-1) > a: -        v = heapq.heappop(q) * (-1) -        L[v - 1] = i + 1 -    heapq.heappush(q, a * (-1)) +for i in reversed(list(range(n))): +    while q: +        if -q[0] > A[i]: +            v = -heapq.heappop(q) +            L[v] = i +        else: +            break +    heapq.heappush(q, -A[i]) +# print(P) +# print(R) -# print(R) -    a = i + 1 -    l, r, p = L[i], R[i], P[i] -    ans += (p - l + 1) * (r - p + 1) * a +    ans += (P[i] - L[i]) * (R[i] - P[i]) * (i + 1)