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
ss = raw_input()
X=map(int, raw_input().split(' '))
N = []
S = []

dR = dict()
for n in range(len(X)) + [len(X)]:
    if n >= len(X): k = -100
    else: 
        #print n
        k = X[n]
    while len(S) > 0 and k < S[-1][1]:
        dR[S[-1][0]] = n - S[-1][0]
        S.pop()

    S.append((n, k))

dL = dict()
for n in list(reversed(range(len(X)))) + [-1]:
    if n < 0: k = -100
    else: 
        k = X[n]
    while len(S) > 0 and k < S[-1][1]:
        dL[S[-1][0]] = abs(n - S[-1][0])
        S.pop()
    S.append((n, k))


ts = 0
for n in xrange(len(X)):
    left = dL[n]
    right = dR[n]
    ts += ((left-1) * (right-1) + left + right - 1) * X[n]

print ts
