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
class _UnionFind:
    __slots__ = ['id']
    def __init__(self, n):
        self.id = [-1] * n
    def find(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.find(self.id[x])
            return self.id[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        res = self.id[x] * self.id[y]
        self.id[x] += self.id[y]
        self.id[y] = x
        return res

N, *A = map(int, open(0).read().split())
uf = _UnionFind(N)
idx = {A[i]: i for i in range(N)}
ans = 0
for a in range(N, 0, -1):
    i = idx[a]
    ans += a
    if i - 1 >= 0 and A[i - 1] > A[i]:
        ans += uf.union(i - 1, i) * a
    if i + 1 < N and A[i + 1] > A[i]:
        ans += uf.union(i + 1, i) * a
print(ans)