2018 - 区间最小值的和
描述

给定数组 A,求

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

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

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

输入

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

接下来n个数字a_i

输出

数组区间最小值的和

样例

输入

3
2 1 3

输出

9

输入

4
1 3 2 4

输出

19

输入

8
5 4 8 1 2 6 7 3

输出

85
提示

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

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

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 20
通过次数 9