题目描述

给定一个序列 $a_1,a_2,a_3,\dots,a_n$，请求出该序列每一个连续子序列的最大值，并计算这些最大值的和。

也就是求出

$$\sum_{1\leq i\leq j\leq n} \max\{a_i,a_{i+1},\cdots,a_j\} $$

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$ 个整数表示 $a_1, a_2,\dots,a_n$

输出格式

• 单个整数：表示所有区间最大数的和

2
6 8

22

样例解释 1

6 + 8 + 8 = 22

3
4 5 6

32

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 500$
• 对于 $60\%$ 的数据，$1\leq n\leq 50,000$
• 对于 $100\%$ 的数据，$1\leq n\leq 500,000$
• $0\leq a_i\leq1,000,000$