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
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
a = map(int, raw_input().split())

aso = [N]*N
q = [a[0]]
for i in xrange(1, N):
    while q and q[-1] > a[i]:
        aso[q[-1] - 1] = i
        q.pop()
    q.append(a[i])
dso = [-1]*N
q = [a[-1]]
for i in xrange(N - 2, -1, -1):
    while q and q[-1] > a[i]:
        dso[q[-1] - 1] = i 
        q.pop()
    q.append(a[i])

ans = 0
for i in xrange(N):
    ans += a[i] * (aso[a[i] - 1] - i)*(i - dso[a[i] - 1])
print ans
