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()))

l = []
r = []
s = []

for i, x in enumerate(a):
    left = i
    while len(s) > 0  and x < s[-1][0]:
        left = s[-1][1]
        s.pop()
        
    l.append(left)    
    s.append([x, left])

s = []
for i in range(n-1, -1, -1):
    right = i
    x = a[i]
    while len(s) > 0  and x < s[-1][0]:
        right = s[-1][1]
        s.pop()
        
    r.append(right)    
    s.append([x, right])
r = r[::-1]

ans = 0    
for i, (x, left, right)  in enumerate(zip(a,l,r)):
    ans += x * (right+1-i) * (i+1-left)
print(ans)

    