2018 - 区间最小值的和
Description

给定数组 A,求

\sum_{i = 1}^n \sum_{j = i}^n \min_{i \leq k \leq j} a_k

数据保证 A[1, n] 的正整数排列。

题面解释,就是区间[i,j]的最小值的和!

Input

一个数字n,表示数组的长度

接下来n个数字a_i

Output

数组区间最小值的和

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
Hint

30%的数据: 1\ ≦\ N\ ≦\ 2,000

100%的数据: 1\ ≦\ N\ ≦\ 200,000 ,a_i\leq N

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 20
通过次数 9