(23-24赛季)稠州常规赛19

P4. 区间最小值的和

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

3
2 1 3

4
1 3 2 4

8
5 4 8 1 2 6 7 3

Hint

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

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

Submit

题目参数

Time Limit	1 second
Memory Limit	128 MB