A row of n crates is stacked left to right, each with a positive integer weight. For every crate, look backward (toward crates placed earlier, to its left) and find the nearest earlier crate whose weight is strictly smaller than the current crate's weight. Report the 1-indexed position of that crate, or 0 if no earlier crate is strictly lighter.
Line 1: an integer n.
Line 2: n space-separated integers, the crate weights from left to right.
n space-separated integers on one line: for each crate (left to right), the 1-indexed position of the nearest earlier strictly-lighter crate, or 0.
Example 1
Input
5 5 3 4 2 6
Expected
0 0 2 0 4
Explanation
Crate 1 (5) has nothing before it: 0. Crate 2 (3): nothing lighter before it: 0. Crate 3 (4): nearest earlier lighter crate is crate 2 (weight 3): 2. Crate 4 (2): nothing lighter before it: 0. Crate 5 (6): nearest earlier lighter crate is crate 4 (weight 2): 4.
Example 2
Input
3 1 2 3
Expected
0 1 2
Explanation
Weights strictly increase, so each crate's immediate predecessor is always lighter: crate 1 has none (0), crate 2's answer is 1, crate 3's answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →