/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は、ハイキングコースの入口に立っています。目の前には、手前から奥に向かって一列に並んだ N 個の山が見えます。手前から i 番目（1 \leq i \leq N）の山の標高は H_i メートルです。
この問題では、山の見え方を次のような簡単なモデルで考えます。山が見えるかどうかは、その山とそれより手前にある山々の標高の大小関係のみで決まります。山どうしの距離は考慮しません。
具体的には、手前から i 番目の山が見えるとは、次の条件を満たすことを意味します。
- 1 \leq j < i を満たすすべての整数 j について H_j < H_i が成り立つ。
言い換えると、手前にある山（1 番目から i-1 番目まで）の中に標高が H_i 以上のものが 1 つでも存在すれば、i 番目の山は手前の山に隠れて見えません。手前に標高がちょうど同じ山がある場合も見えないことに注意してください。
最も手前にある山（1 番目の山）は、それより手前に山が存在しないため、必ず見えます。
高橋君から見える山の番号（1 から N までの整数）をすべて求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- 入力はすべて整数
入力
N H_1 H_2 \ldots H_N
- 1 行目には、山の数を表す整数 N が与えられる。
- 2 行目には、手前から i 番目（i = 1, 2, \ldots, N）の山の標高（メートル）を表す整数 H_i が、スペース区切りで N 個与えられる。
出力
見える山の番号を小さい順に、スペース区切りで 1 行に出力せよ。末尾に余分なスペースがあっても構わない。
入力例 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
Score : 233 pts
Problem Statement
Takahashi is standing at the entrance of a hiking course. In front of him, he can see N mountains lined up in a row from front to back. The elevation of the i-th mountain from the front (1 \leq i \leq N) is H_i meters.
In this problem, we consider the visibility of mountains using the following simple model. Whether a mountain is visible or not is determined solely by the relative heights of that mountain and the mountains in front of it. The distances between mountains are not considered.
Specifically, the i-th mountain from the front is visible if and only if the following condition is satisfied:
- For every integer j satisfying 1 \leq j < i, H_j < H_i holds.
In other words, if there exists even one mountain among the mountains in front (from the 1-st to the (i-1)-th) whose elevation is H_i or greater, then the i-th mountain is hidden behind a mountain in front and is not visible. Note that a mountain is also not visible if there is a mountain in front with exactly the same elevation.
The frontmost mountain (the 1-st mountain) is always visible since there are no mountains in front of it.
Find all the numbers (integers from 1 to N) of the mountains visible to Takahashi.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- All input values are integers.
Input
N H_1 H_2 \ldots H_N
- The first line contains an integer N representing the number of mountains.
- The second line contains N integers H_i separated by spaces, where H_i represents the elevation (in meters) of the i-th mountain from the front (i = 1, 2, \ldots, N).
Output
Print the numbers of the visible mountains in ascending order on a single line, separated by spaces. Trailing spaces are acceptable.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
1 3 5
Sample Input 2
8 10 20 15 25 5 30 28 35
Sample Output 2
1 2 4 6 8
Sample Input 3
15 100 50 80 120 110 130 125 140 200 150 180 250 240 300 299
Sample Output 3
1 4 6 8 9 12 14