Students stand in a line with heights h[0..n−1]. For each student, find the height of the first student to their right who is strictly taller. If there is none, write -1.
Constraints
- 1 ≤ n ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: n integers.
- Output
- n integers on one line.
Examples
Input 1
4
4 5 2 25Output
5 25 25 -14 → 5, 5 → 25, 2 → 25, and nothing is taller than 25.
Input 2
4
13 7 6 12Output
-1 12 12 -113 has nothing taller to its right; 7 and 6 both see 12 first.
Show hints
- Scan from the right and keep a stack of candidates.
- Pop every candidate that is not taller than the current student — they can never be the answer for anyone further left.
Show the explanation
A monotonic stack solves it in one pass from the right. The stack holds heights in decreasing order from bottom to top. For each student, pop while the top is ≤ their height (those students are hidden behind this one for everyone to the left). The top, if any, is the answer; then push the current height. Each height is pushed and popped at most once, so the total is O(n).
Original UniCircle question. Last reviewed 22 Oct 2026.