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:
	"0-indexed apparently"
	
	def __init__(self, n):
		self.n = n
		self.data = [0] * (n+1)
		
	def point_add(self, index, value):
		index += 1
		while index <= self.n:
			self.data[index] += value
			index += index & -index
		
	def folded(self, r):
		"[0, r)"
		ret = 0
		while r > 0:
			ret += self.data[r]
			r -= r & -r
		return ret
		
	def bisect_left(self, value):
		index = 0
		k = 1 << ((self.n + 1).bit_length() - 1)
		while k > 0:
			if index + k <= self.n and self.data[index + k] < value:
				value -= self.data[index + k]
				index += k
			k >>= 1
		return index + 1
		
N = int(input())
As = list(map(int, input().split()))

A_inv = [0] * N
for i, A in enumerate(As):
	A_inv[A-1] = i
	
bit = BIT(N + 2)
bit.point_add(0, 1)
bit.point_add(N+1, 1)
ans = 0
for A, index in enumerate(A_inv):
	A += 1
	index += 1
	v = bit.folded(index)
	ans += A * (bit.bisect_left(v+1) - index - 1) * (index - bit.bisect_left(v) + 1)
	#print(A, ans)
	bit.point_add(index, 1)
	
print(ans)