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
N = int(input())
A = list(map(int, input().split()))

b = [0]*(N+1)
l = [i for i in range(N+2)] # 最初と最後に番兵の役割
r = [i for i in range(N+2)]

ans = 0
for i in range(N):
  b[A[i]] = i#各数字がAのどこに入っているかをリストbにメモ
  
for i in range(N, 0, -1)  :
  m = b[i]#大きな数字がどこに入っているかを探す
  x, y = l[m], r[m] #その時の左右に動ける大きさをとってくる
  ans += i * (m- x+1) * (y - m+1) #その数が何回使えるかを計算し、答えに追加
  l[y + 1], r[x - 1] = x, y #動ける範囲を次の場所に代入
print(ans)  
  