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
def main():
	n, *a = map(int, open(0).read().split())
	idc = [0] * (n + 1)
	R = list(range(n + 2))
	L = R[:]
	ans = 0
	for i in range(n):
		idc[a[i]] = i + 1
	for x in range(n, 0, -1):
		i = idc[x]
		M = R[i]
		m = L[i]
		ans += x * (M - i + 1) * (i - m + 1)
		# とくに変更済みのとき連結
		R[m - 1] = M
		L[M + 1] = m
	print(ans)

if __name__=="__main__":
	main()
