eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Go up the Ultras

Go up the Ultras

The topographic prominence of a peak is a measure of special interest to mountain climbers and can be defined as follows: the prominence of a peak \textbf{p} with altitude \textbf{h}, relative to the sea level, is the greatest d such that any path on the terrain from \textbf{p} to any strictly higher peak will pass through a point of altitude \textbf{h-d}. If there is no strictly higher peak, then the prominence is \textbf{h} itself. Those peaks with topographic prominence greater than or equal to \textbf{150000} centimeters (precision is of great importance to climbers!) have a special name: they are called "Ultras". You have to write a program that identifies all the Ultras that occur in a two dimensional profile of a mountain range represented as a sequence of points. Note that the horizontal distance between points is not important; all that you need is the altitude of each point. In the picture below, the Ultras are the points \textbf{7}, \textbf{12}, \textbf{14}, \textbf{20} and \textbf{23}. \includegraphics{https://static.e-olymp.com/content/48/484d9a4f0fe796aed1dd37cefc5f839bed9d7813.jpg} \InputFile The first line contains an integer \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{10^5}) representing the number of points in the profile. The second line contains \textbf{N} integers \textbf{H_i} indicating the altitudes (in centimeters) of the points, in the order in which they appear in the profile (\textbf{0} ≤ \textbf{Hi} ≤ \textbf{10^6} for \textbf{i =} \textbf{1}, \textbf{2}, ..., \textbf{N}). Consecutive points have different altitudes (\textbf{H_i} ≠ \textbf{H_\{i+1\}} for \textbf{i = 1}, \textbf{2}, ..., \textbf{N-1}), while the first and the last points are at sea level (\textbf{H_1 = H_N = 0}). You may assume that the profile contains at least one Ultra. \OutputFile Output a line with the indices of all the Ultras in the mountain range, in the order in which they appear in the profile.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
5
0 10000 100000 884813 0
Выходные данные #1
4
Автор Guilherme Albuquerque Pinto
Источник ACM ICPC Regional Latino America 2013