Problem H
Topographic Isolation
As a mountaineer, you are interested in the most impressive mountains. One way of comparing mountains against each other is their topographic isolation. The topographic isolation of a mountain is the minimal horizontal distance you would have to travel from the peak to reach another point of equal or higher elevation.
You are given a 1D array, representing the elevations of different points on a straight line. A peak is defined as any point where the adjacent points are both strictly lower than the current point (so the edges of the array are never peaks). For each peak, determine if it has a topographic isolation, and if it does, calculate it.
Input
The first line of input contains an integer $n$ ($3 \leq n \leq 2 \times 10^5$), the size of the array.
The next line of input contains $n$ space-seperated integers $1 \leq h_1, h_2, \ldots , h_n \leq 10^9$, the elevation of different points along the straight line.
Output
Output a line containing $n$ space-seperated integers $a_1, a_2, \ldots , a_n$, where for all $1 \leq i \leq n$, the following conditions for $a_i$ must be met.
If the $i^\text {th}$ point is not a peak, $a_i = 0$.
Otherwise, if the $i^\text {th}$ point is a peak but has no topographic isolation because an equal or higher point does not exist, $a_i = -1$.
And finally, if the $i^\text {th}$ point is a peak and has a topographic isolation, $a_i$ is equal to the topographic isolation.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 3 2 10 2 |
0 2 0 -1 0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 6 2 1 1 4 3 1 5 2 4 |
0 0 0 0 3 0 0 7 0 0 |
