U478856 区间最值和
题目描述
给定一个长度为 n 的序列 a。
你需要求出所有区间的最大值之和。
即对于所有的$1\leq L \leq R \leq n$, 均存在 $max(a[L],...,a[R)$, 求出 $\sum max(a_L,...,a_R)$。
输入格式
第一行 n。
第二行 n 个正整数。
输出格式
一行一个数表示答案。
说明/提示
对于 100% 的数据，$ 1 \leq n \leq 1e6, 1 \leq a_i \leq 1e9$。