该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

也就是求出

输入格式

• 第一行：单个整数 $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$