Question
Next Stronger Tower
In a futuristic city, a straight highway is guarded by N energy towers placed from left to right. Each tower has a certain strength level, recorded in an array A, where A[i] denotes the strength of the i-th tower.
For safety analysis, the city control system wants to know, for each tower, whether there exists a stronger tower ahead of it that could overpower its signal.
To model this, another array B is defined as follows:
-
B[i] = A[j], where j > i and A[j] > A[i], and j is the smallest possible index satisfying this condition.
-
If no such index j exists, then B[i] = -1.
Your task is to compute the array B for all towers.
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
6
5 3 8 4 10 2
Output
8 8 10 10 -1 -1
Explanation:
Tower 0 (strength 5): the next stronger tower is at index 2 with strength 8.
Tower 1 (strength 3): the next stronger tower is also at index 2 with strength 8.
Tower 2 (strength 8): the next stronger tower is at index 4 with strength 10.
Tower 3 (strength 4): the next stronger tower is at index 4 with strength 10.
Tower 4 (strength 10): no stronger tower exists to its right → -1.
Tower 5 (strength 2): no tower to its right → -1.
So, the resulting array B is: [8, 8, 10, 10, -1, -1].
6
5 3 8 4 10 2
Output
8 8 10 10 -1 -1
Explanation:
Tower 0 (strength 5): the next stronger tower is at index 2 with strength 8.
Tower 1 (strength 3): the next stronger tower is also at index 2 with strength 8.
Tower 2 (strength 8): the next stronger tower is at index 4 with strength 10.
Tower 3 (strength 4): the next stronger tower is at index 4 with strength 10.
Tower 4 (strength 10): no stronger tower exists to its right → -1.
Tower 5 (strength 2): no tower to its right → -1.
So, the resulting array B is: [8, 8, 10, 10, -1, -1].