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 BIT_index:
    def __init__(self, n):
        self.BIT_prev = [n] * (n + 1)
        self.BIT_next = [n] * (n + 1)
        self.n = n

    def __addElement(self, BIT, idx):
        value = idx
        idx += 1
        while idx > 0:
            BIT[idx] = min(BIT[idx], value)
            idx -= idx & -idx

    def addElement(self, idx):
        self.__addElement(self.BIT_prev, self.n - 1 - idx)
        self.__addElement(self.BIT_next, idx)

    def __getIndex(self, BIT, idx):
        idx += 1
        ans = self.n
        while idx <= self.n:
            ans = min(ans, BIT[idx])
            idx += idx & -idx
        return ans

    def getIndexPrev(self, idx):
        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)

    def getIndexNext(self, idx):
        return self.__getIndex(self.BIT_next, idx)


N = int(input())
As = list(map(int, input().split()))

Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]

BIT = BIT_index(N)
ans = 0
for i, B in enumerate(Bs):
    iN = BIT.getIndexNext(B)
    iP = BIT.getIndexPrev(B)
    BIT.addElement(B)
    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))

print(ans)
