Mines

Time limit2sMemory limit128 MB

Summary

Given N mines in a line with chain-reaction explosion rules based on impact strength, find the minimum set of mines to directly detonate so all mines explode.

Level: Medium6 of 10
Topics: Greedy, Simulation, Array
Solved: No attempts yet

Problem

There are N mines placed at equal intervals on a straight line. The impact strength of the i-th mine is P_i.

When a mine explodes, it applies force equal to its own impact strength to the nearest unexploded mine on each side. A mine that receives force explodes only if the force is strictly greater than its impact strength, and then it applies its own impact strength to its neighbors in the same way. If the received force is less than or equal to the mine's impact strength, the chain reaction stops in that direction.

You may directly detonate several mines. Find the numbers of the mines that must be directly detonated when the number of direct detonations is minimized while still exploding every mine.

Input

The first line contains the number of mines N. Each of the next N lines contains the impact strength P_i of one mine, in order from mine 1 to mine N.

Output

Print the numbers of the mines that must be directly detonated in increasing order, one per line.

Constraints

1 <= N <= 50,000
1 <= P_i <= 10,000

Examples1

Example 1
Input
```
9
1
2
5
4
3
3
6
6
2
```
Expected output
```
3
7
8
```