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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

ans = 0
L = Bit(n)
R = Bit(n)

B = [[A[i], i, n-i-1] for i in range(n)]
B.sort()
for i in range(n):
    # print(*[L.sum(i) for i in range(1, n+1)])
    ind = B[i][1]+1
    l = 0
    r = ind+1
    m = (l+r)//2
    lind = L.sum(ind)
    while r-l>1:
        if L.sum(m)< lind:
            l = m
        else:
            r = m
        m = (l+r)//2
    a = l
    L.add(ind+1, 1)
    # print(ind-1,a)

    ind = B[i][2]+1
    l = 0
    r = ind+1
    m = (l+r)//2
    rind = R.sum(ind)
    while r-l>1:
        if R.sum(m) < rind:
            l = m
        else:
            r = m
        m = (l+r)//2
    b = l
    R.add(ind+1, 1)

    ans += (i+1) * (B[i][1]+1 - a) * (n+1-b - (B[i][1]+1))
    # print(i+1, B[i][1]+1, a, n+1-b, ans)


print(ans)