分数: 466 分
问题陈述
N 人们从左到右站成一排,高度 i左起第一个人 (1 \leq i \leq N) is H_i。多个人可能具有相同的身高。
每个 N 人们拿着一个球并将其扔到右侧。球由 i第一个人被 最左边的人 在那些在右边的人中 i第一个人和是 严格更高 比 i第一个人。即球被最小的对应的人接住 j 满意 j > i 和 H_j > H_i。如果没有这样的人存在,则球不会被任何人接住。
当 j- 第一个人接住由 i- 第人 (i < j), 成本 本次转移的 被定义为所有人员中的最低身高 i-th 和 j- 第人(包括 i-th 和 j- 第一个人自己),即 \min(H_i, H_{i+1}, \ldots, H_j)。没有人接住球的成本是 0.
求每个人抛出的球的转移成本总和 N 人。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- 所有输入均为整数
输入
N H_1 H_2 \ldots H_N
- 第一行包含一个整数 N 代表人数。
- 第二行包含 N 整数 H_i 以空格分隔,代表高度 i左起第一个人 (i = 1, 2, \ldots, N).
输出
在一行中输出每个人抛出的球的转移成本总和 N 人。
示例输入 1
5 3 1 4 1 5
示例输出 1
4
示例输入 2
4 5 5 5 5
示例输出 2
0
示例输入 3
8 2 7 3 5 1 6 4 8
示例输出 3
16
示例输入 4
15 10 3 7 2 8 1 5 12 4 6 9 3 11 2 15
示例输出 4
37
示例输入 5
1 1000000000
示例输出 5
0