One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

<image>

Constraints

* 1 ≦ N ≦ 200,000
* (a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Examples

Input

3
2 1 3


Output

9


Input

4
1 3 2 4


Output

19


Input

8
5 4 8 1 2 6 7 3


Output

85
n = int(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(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)
