← 返回题目列表

AtCoder · awc0035_e

E. 山脉景观

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

分数: 466 分

问题陈述

高桥正在山区徒步旅行。在这个地区, N 山脉排列成一排,海拔高度 i左边数第一座山是 H_i.

高桥站在每座山的山顶,向左看(指数递减的方向)。他喜欢计算有多少座满足特定条件的山脉是可见的。

从山顶向左看时 i, 山 j (j < i) 是 可见 当且仅当满足以下两个条件时:

  1. H_j > H_i。也就是山 j 严格高于山 i。特别是,如果 H_j = H_i, 山 j 不被视为可见。
  2. 对于所有整数 k 满意 j < k < i, H_k < H_j 成立。也就是山与山之间的所有山 j 和山 i 的海拔严格低于 H_j.

条件2表示如果山之间有一座山 j 和山 i 海拔大于或等于 H_j,然后是山 j 已被阻止且不可见。当 j = i - 1 (即山 j 和山 i 相邻),它们之间没有山脉,因此自动满足条件 2。

请注意,该问题中“可见”的定义如上所述,并且与真实视线遮挡的物理模型不同。

让 C_i 是从山顶左侧可见的山脉数量 i。因为山的左边没有山 1, C_1 = 0.

求总和 C_i 对于所有人 i = 1, 2, \ldots, N,即 \displaystyle\sum_{i=1}^{N} C_i.

约束

  • 1 \leq N \leq 10^6
  • 1 \leq H_i \leq 10^9
  • 所有输入均为整数。
  • 可能有多座海拔相同的山。

输入

N
H_1 H_2 \ldots H_N
  • 第一行包含一个整数 N 代表山脉的数量。
  • 第二行包含 N 整数 H_1, H_2, \ldots, H_N 以空格分隔,代表每座山的海拔。

输出

输出值 \displaystyle\sum_{i=1}^{N} C_i 在一行上。


示例输入 1

5
3 1 4 1 5

示例输出 1

2

示例输入 2

5
2 3 1 2 1

示例输出 2

4

示例输入 3

10
5 3 8 6 7 2 9 1 4 3

示例输出 3

9

示例输入 4

20
10 4 15 7 12 3 18 6 14 2 20 8 16 5 11 1 19 9 13 17

示例输出 4

25

示例输入 5

1
1000000000

示例输出 5

0