← 返回题目列表

AtCoder · awc0038_a

A. 山景城

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

分数: 233 分

问题陈述

高桥正站在远足路线的入口处。在他面前,他可以看到 N 山从前到后排成一排。的海拔 i从前面数第一座山 (1 \leq i \leq N) 是 H_i 米。

在这个问题中,我们使用以下简单模型来考虑山脉的可见性。一座山是否可见,完全取决于该山和它前面的山的相对高度。不考虑山之间的距离。

具体来说, i从前面数第一座山是 可见 当且仅当满足以下条件时:

  • 对于每个整数 j 满意 1 \leq j < i, H_j < H_i 成立。

换句话说,如果前面的山中存在哪怕一座山(从 1-st 到 (i-1)-th) 其海拔为 H_i 或更大,则 i第一座山隐藏在前面的一座山后面,不可见。请注意,如果前面有一座海拔完全相同的山,那么山也是不可见的。

最前面的山( 1-st 山)始终可见,因为它前面没有山。

查找所有数字(整数来自 1 to 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 以空格分隔,其中 H_i 代表海拔高度(以米为单位) i从前面数第一座山 (i = 1, 2, \ldots, N).

输出

在一行上按升序打印可见山脉的编号,并用空格分隔。尾随空格是可以接受的。


示例输入 1

5
3 1 4 1 5

示例输出 1

1 3 5

示例输入 2

8
10 20 15 25 5 30 28 35

示例输出 2

1 2 4 6 8

示例输入 3

15
100 50 80 120 110 130 125 140 200 150 180 250 240 300 299

示例输出 3

1 4 6 8 9 12 14