This page is still under construction.

Parts of this page are still being built. What you see may change.

Go up the Ultras

Time limit1sMemory limit128 MB

Summary
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 pp whose altitude above sea level is hh, the prominence of pp is the greatest dd such that every path along the terrain from pp to any strictly higher peak passes through a point of altitude h−dh - d. If there is no strictly higher peak, the prominence is hh 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 NN, the number of points in the profile (3≤N≤1053 \le N \le 10^5). The second line contains the altitudes H1,H2,…,HNH_1, H_2, \dots, H_N of the points in centimeters, in the order in which they appear in the profile (0≤Hi≤1060 \le H_i \le 10^6). Consecutive points have different altitudes (Hi≠Hi+1H_i \ne H_{i+1} for i=1,2,…,N−1i = 1, 2, \dots, N-1). The first and the last point are at sea level (H1=HN=0H_1 = H_N = 0). 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.

Examples1

  1. Example 1

    Input
    5
    0 10000 100000 884813 0
    
    Expected output
    4