← 返回题目列表

AtCoder · awc0037_e

E. 万向球

中文机器翻译题面 查看原题

分数: 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