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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def tree_size(self, x):
        return self.size[self.find(x)]


N = int(input())
a = [-1] + [int(_) for _ in input().split()] + [-1]
uf = UnionFind(N+1)
place = [-1]*(N+1)
ans = 0

for i in range(1, N+1):
    place[a[i]] = i

for i in range(N, 0, -1):
    left = right = 0
    if a[place[i]] < a[place[i]-1]:
        left = uf.tree_size(uf.find(a[place[i]-1]))
        uf.unite(a[place[i]], a[place[i]-1])
    
    if a[place[i]] < a[place[i]+1]:
        right = uf.tree_size(uf.find(a[place[i]+1]))
        uf.unite(a[place[i]], a[place[i]+1])
    
    ans += (left+1)*(right+1)*a[place[i]]

print(ans)