eolymp
bolt
Try our new interface for solving problems
Problems

Go up the Ultras

Go up the Ultras

Time limit 1 second
Memory limit 64 MiB

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 p with altitude h, relative to the sea level, is the greatest d such that any path on the terrain from p to any strictly higher peak will pass through a point of altitude h-d. If there is no strictly higher peak, then the prominence is h itself. Those peaks with topographic prominence greater than or equal to 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 7, 12, 14, 20 and 23.

Input data

The first line contains an integer N (3N10^5) representing the number of points in the profile. The second line contains N integers H_i indicating the altitudes (in centimeters) of the points, in the order in which they appear in the profile (0Hi10^6 for i =1, 2, ..., N). Consecutive points have different altitudes (H_iH_{i+1} for i = 1, 2, ..., N-1), while the first and the last points are at sea level (H_1 = H_N = 0). You may assume that the profile contains at least one Ultra.

Output data

Output a line with the indices of all the Ultras in the mountain range, in the order in which they appear in the profile.

Examples

Input example #1
5
0 10000 100000 884813 0
Output example #1
4
Author Guilherme Albuquerque Pinto
Source ACM ICPC Regional Latino America 2013