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
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
すべてのiに対して
「a_iが最小値となる区間はいくつあるか?」を考える.
a_iより左側でa_iより小さいもののうち最もa_iに近いものをa_l
a_iより右側でa_iより小さいもののうち最もa_iに近いものをa_rとする.
最小値がa_iとなる区間は左側がl+1,l+2,...,i
                    　右側がi,i+1,...,r-1となる区間
⇒(i-l+1)x(r-i+1)個の区間でa_iが最小値をとる
すべてのiに対してこの個数を求める.
"""

n = I()
a = LI()
lst = [0]*(n+1)

for i in range(n):
    lst[a[i]] = i

l = [0]*n #各iに対して,a_iより左側でa_iより小さいもののうち最もa_iに近いもののindex
r = [0]*n #各iに対して,a_iより右側でa_iより小さいもののうち最もa_iに近いもののindex
ans = 0

#大きい値から見ていく
for x in range(1,n+1)[::-1]:
    #調べている数 := x
    #xの位置 := i
    i = lst[x]

    #iが右端でないかつ,iの右隣が自分(x)より大きい場合
    if i+1 < n and a[i+1] > x:
        #r[i+1] := iより右側でxより小さいもののうち最もiに近いもののindex
        #  ⇒ i <= j < r[i+1] に関してa[j]はx以上である.
        R = r[i+1]
    else:
        #右隣がいないまたは右隣が自分(x)より小さい場合
        R = i
    
    #iが左端でないかつ,iの左隣が自分(x)より大きい場合
    if i-1 >= 0 and a[i-1] > x:
        #l[i-1] := iより左側でxより小さいもののうち最もiに近いもののindex
        #  ⇒ l[i-1] < j <= i に関してa[j]はx以上である.
        L = l[i-1]
    else:
        #左隣がいないまたは左隣が自分(x)より小さい場合
        L = i
    
    # L < j < Rに関してa[j]はx以上であることが分かっている.
    # ⇒Rの位置から見て左側の区間はLまで
    # ⇒Lの位置から見て右側の区間はRまで
    l[R] = L
    r[L] = R
    ans += (i-L+1)*(R-i+1)*x
print(ans)
    