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())
l=[int(i) for i in input().split()]

def f(l):
    p=[0]*(n+1)
    s=[(-1,0)] #sentinel
    for i,a in enumerate(l):
        while s[-1][1]>a: #delete items if larger than target
            s.pop()
        t=i-s[-1][0] #get distance(left--target)
        p[a]=t #P[x] means distance(left--x) its min equals to x
        s.extend([(i,a)]) #add items
    return p
p=f(l) #distance list (left--target)
q=f(l[::-1]) #distance list (target--right)
print(sum(i*p[i]*q[i] for i in l))
