题目描述

输入一个 $1\sim n$ 的排列 $a$。请你找到 $a$ 的所有子区间的最大值之和为多少。

输入格式

第一行一个数 $n$。

第二行 $n$ 个数 $a_1\sim a_n$。

输出格式

一个数，即所有子区间的最大值之和

4
3 2 4 1

33

• 子区间有 [3] [2] [4] [1] [3,2] [2,4] [4,1] [3,2,4] [2,4,1] [3,2,4,1]
• 对应的最大值为 3 2 4 1 3 4 4 4 4 4
• 和为 $3+2+4+1+3+4+4+4+4+4=33$

5
1 2 3 4 5

55

数据规模与约定

共五个子任务，子任务 $i$ 的 $n$ 为 $5\times 10^i$