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 itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def gutyocu():
    ans = 0
    for i, j in itertools.combinations_with_replacement(range(N), r=2):
        ans += min(A[i: j + 1])
    return ans


pos = list(range(N + 1))
pos[0] = -1
for i, a in enumerate(A):
    pos[a] = i

ans = 0
lefts = list(range(N + 1))
rights = list(range(N + 1))
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        # 右とつながった
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        # 左とつながった
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (abs(left - p) + 1) * (abs(right - p) + 1) * i
print(ans)
