图书管理员把 N 本书排成一排放上新书架，从左到右编号 1, 2, \dots, N，第 i 本书的高度恰好是 a_i。可以保证 a_1, a_2, \dots, a_N 是 1, 2, \dots, N 的一个排列。

对于每一段连续的区间 [l, r]（1 \le l \le r \le N），定义它的高度为该区间内最矮一本书的高度，即 \min(a_l, a_{l+1}, \dots, a_r)。

请求出所有 \dfrac{N(N+1)}{2} 个区间的高度之和：

\sum_{1 \le l \le r \le N} \min(a_l, a_{l+1}, \dots, a_r)

第一行一个整数 N。

第二行 N 个整数 a_1, a_2, \dots, a_N。

输出一行一个整数，表示答案。注意答案可能超过 32 位整数范围。

样例 1：6 个区间 [1,1],[1,2],[1,3],[2,2],[2,3],[3,3] 的最小值依次为 2,1,1,1,1,3，和为 9。

对于全部数据，保证 1 \le N \le 2\times 10^5，(a_1,\dots,a_N) 是 (1,\dots,N) 的一个排列。

| 20% | 1~5 | 20 | N \le 100 | 

| 60% | 6~15 | 40（累计 60） | N \le 3000 | 

| 100% | 16~25 | 40（累计 100） | N \le 2\times 10^5 |