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
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
a = list(map(int,input().split()))
b = [0]*(N+1)
left,right = [i for i in range(N+2)],[i for i in range(N+2)]
ans = 0
for i in range(N):
    b[a[i]] = i
for i in range(N+1)[::-1]:
    m = b[i]
    l,r = left[m],right[m]
    ans += i*(m-l+1)*(r-m+1)
    left[r+1]=l
    right[l-1]=r
print(ans)