p03987 AtCoder Grand Contest 005 - Minimum Sum
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
```python
import sys
input = sys.stdin.readline
import bisect

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

B = [[A[i], i] for i in range(n)]
B.sort()

L = Bit(n)
R = Bit(n)
ans = 0
for i in range(n):
    l = -1
    r = n+1
    m = (l+r)//2
    while r-l > 1:
        # print(L.sum(m) , i,l,r,m)
        if L.sum(m) < L.sum(B[i][1]+1):
            l = m
        else:
            r = m
        m = (l+r)//2
    # print(l)
    L.add(B[i][1]+1, 1)
    # print([L.sum(i+1)-L.sum(i) for i in range(n)])
    # print([L.sum(i+1) for i in range(n)])
    LL = l

    rr = n-1-B[i][1]
    l = -1
    r = n+1
    m = (l+r)//2
    while r-l > 1:
        # print(R.sum(m) , i,l,r,m)
        if R.sum(m) < R.sum(rr+1):
            l = m
        else:
            r = m
        m = (l+r)//2
    # print("R", l)
    R.add(n-1-B[i][1]+1, 1)
    # print([R.sum(i+1)-R.sum(i) for i in range(n)])
    RR = l

    ans += B[i][0] * (B[i][1]-LL) * ((n-1-RR)-B[i][1])
    # print("ans", ans)
print(ans)
```