Towers
Time limit1.5sMemory limit128 MB
For each tower in a line, find the nearest tower to its left with height at least as large, using a monotonic stack approach.
Problem
N towers with different heights stand in a line from left to right. Each tower has a laser transmitter at its top, and every transmitter sends its signal horizontally to the left. A signal can be received only by the first tower it meets. Therefore, the signal from a tower is received by the nearest tower to its left whose height is at least the current tower's height. If no such tower exists, the signal is not received.
For each tower, write a program that finds the number of the tower that receives its signal. Towers are numbered from 1 on the left.
Input
The first line contains an integer N, the number of towers. N is between 1 and 500,000 inclusive.
The second line contains N integers, the tower heights from left to right, separated by spaces. Each height is an integer between 1 and 100,000,000 inclusive.
Output
Print one line containing, in tower order, the number of the tower that receives each tower's signal. Print 0 if no tower receives the signal. Separate the values with spaces.