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.readline
sys.setrecursionlimit(10**9)
import heapq
n=int(input())
A=list(map(int,input().split()))
idx={}
for i,a in enumerate(A):
    idx[a]=i
hq=[]
right=[n-1]*n
for i in range(n):
    while hq and -hq[0]>A[i]:
        h=-heapq.heappop(hq)
        right[idx[h]]=i-1
    heapq.heappush(hq,-A[i])
hq=[]
left=[0]*n
for i in range(n-1,-1,-1):
    while hq and -hq[0]>A[i]:
        h=-heapq.heappop(hq)
        left[idx[h]]=i+1
    heapq.heappush(hq,-A[i])
ans=0
for i in range(n):
    ans+=A[i]*(i-left[i]+1)*(right[i]-i+1)
print(ans)