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 random
import time
# Treap

# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root
    x=root
    ans=10**20
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans



N=int(input())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

random.seed()
randint=random.randint

insert(function[0],randint(1,200000))
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if search1(function[i])!=-1:
        data1[i]=search1(function[i])
    else:
        data1[i]=-1
    if search2(function[i])!=10**20:
        data2[i]=search2(function[i])
    else:
        data2[i]=N
    insert(function[i],randint(1,200000))

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)