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
class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n

    def root(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.root(self.id[x])
            return self.id[x]

    def find(self, x, y):
        return uf.root(x) == uf.root(y)

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            return True
        return False

n = int(input())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans=0
data=[0]*n
b=[0]*(n+1)
for i in range(n):
    b[a[i]]=i
for i in range(n,0,-1):
    r,l=0,0
    data[b[i]]=i
    if b[i]+1 <= n-1:
        if data[b[i]+1]>0:
            uf.union(b[i],b[i]+1)
    r=-uf.id[uf.root(b[i])]

    if b[i]-1>=0 and data[b[i]-1]>0:
        uf.union(b[i],b[i]-1)
    l=1-uf.id[uf.root(b[i])]-r
    ans+=(r*l)*i
print(ans)


