Question
The Search for a Weaker Signal
In a futuristic city, a long street is lined with N signal towers, each having a certain power level. These power levels are recorded in an array A, where A[i] represents the power of the i-th tower from left to right.
For every tower, the city’s monitoring system wants to know the next weaker tower that appears to its right. This information helps engineers predict potential signal interference.
To do this, another array B is defined as follows:
-
B[i] is the power level of the first tower to the right of i (that is, at some index j > i) such that A[j] < A[i].
-
If there is no such tower to the right of tower i, then B[i] = -1.
Your task is to help the engineers compute the array B based on the given array A.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of signal towers.
The second line contains KaTeX can only parse string typed expression space-separated integers
KaTeX can only parse string typed expression — representing the power levels of the towers.
The second line contains KaTeX can only parse string typed expression space-separated integers
KaTeX can only parse string typed expression — representing the power levels of the towers.
Output
Print KaTeX can only parse string typed expression space-separated integers representing the array
KaTeX can only parse string typed expression, where each value follows the rule described above.
KaTeX can only parse string typed expression, where each value follows the rule described above.
Example
Input
5
4 8 5 2 25
Output
2 5 2 -1 -1
Explanation:
For tower 0 (power 4), the next weaker tower is at index 3 with power 2.
For tower 1 (power 8), the next weaker tower is at index 2 with power 5.
For tower 2 (power 5), the next weaker tower is at index 3 with power 2.
For tower 3 (power 2), there is no weaker tower to its right → -1.
For tower 4 (power 25), there is no tower to its right → -1.
So, the final array B is: [2, 5, 2, -1, -1]
5
4 8 5 2 25
Output
2 5 2 -1 -1
Explanation:
For tower 0 (power 4), the next weaker tower is at index 3 with power 2.
For tower 1 (power 8), the next weaker tower is at index 2 with power 5.
For tower 2 (power 5), the next weaker tower is at index 3 with power 2.
For tower 3 (power 2), there is no weaker tower to its right → -1.
For tower 4 (power 25), there is no tower to its right → -1.
So, the final array B is: [2, 5, 2, -1, -1]