Go up the Ultras
Time limit1sMemory limit128 MB
The program reads an altitude profile of up to 100000 points and prints the indices of every peak with prominence of at least 150000 centimeters.
- Level
Medium7 of 10
- Topics
- Stack, Segment tree
- Solved
- No attempts yet
Problem
The topographic prominence of a peak is a measure that matters a great deal to mountain climbers, and it is defined as follows. For a peak whose altitude above sea level is , the prominence of is the greatest such that every path along the terrain from to any strictly higher peak passes through a point of altitude . If there is no strictly higher peak, the prominence is itself.
Peaks with a topographic prominence of 150000 centimeters or more (precision is of great importance to climbers!) have a special name: they are called Ultras.
A two dimensional profile of a mountain range is given as a sequence of points. Write a program that identifies every Ultra in that profile. The horizontal distance between points does not matter, only the altitude of each point. In the profile a peak is a point higher than both of its neighbours, so the first and the last point are never peaks.
Input
The first line contains an integer , the number of points in the profile (). The second line contains the altitudes of the points in centimeters, in the order in which they appear in the profile (). Consecutive points have different altitudes ( for ). The first and the last point are at sea level (). The profile contains at least one Ultra.
Output
Print the indices of all the Ultras on one line, separated by single spaces, in the order in which they appear in the profile. Indices start at 1.