经历了与 Laffey 一下午的斗争之后，Star 开始对那道题跑的最快的算法产生了兴趣，于是他跑过来加了一道题......
给定一个长度为 n 的序列，求序列中每一个区间的最大值之和。
第 1 行一个整数 n 表示序列的长度。
第 2 行 n 个整数 a_i ，表示序列中的第 i 个数。
一个整数表示区间最大值之和。
10 8 9 2 7 7 7 5 0 1 6
388
对于前 40\% 的数据，满足 0 < n \le 10^3 。
对于前 60\% 的数据，满足 0 < n \le 10^5 。
对于 100\% 的数据，满足 0 <n \le 10^7 。
对于所有的 a_i ，满足 |a_i| \le 10^5 。