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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_range(A):
    smaller = [[0, -1]]
    ret = []
    for i, a in enumerate(A):
        while smaller[-1][0] > a:
            smaller.pop()
        ret.append(i-smaller[-1][1])
        smaller.append([a, i])
    return ret

B = min_range(A)
C = min_range(A[::-1])[::-1]

answer = 0
for i in range(N):
    answer += A[i] * B[i] * C[i]

print(answer)

