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
import sys
input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, input().split()))

def while_pop(arr):
    res = [0] * N
    tmp = []
    for i, a in enumerate(arr):
        cnt = 1
        while tmp:
            aa, c = tmp.pop()
            if aa < a:
                tmp.append((aa, c))
                break
            else:
                cnt += c
        tmp.append((a, cnt))
        res[i] = cnt
    return res

left = while_pop(A)
right = while_pop(A[::-1])[::-1]

answer = 0
for i in range(N):
    answer += left[i] * right[i] * A[i]
    
print(answer)