分数: 466 分
问题陈述
高桥正在山区徒步旅行。在这个地区, N 山脉排列成一排,海拔高度 i左边数第一座山是 H_i.
高桥站在每座山的山顶,向左看(指数递减的方向)。他喜欢计算有多少座满足特定条件的山脉是可见的。
从山顶向左看时 i, 山 j (j < i) 是 可见 当且仅当满足以下两个条件时:
- H_j > H_i。也就是山 j 严格高于山 i。特别是,如果 H_j = H_i, 山 j 不被视为可见。
- 对于所有整数 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