A queue issued n tickets in order, numbered by the value printed on each ticket (not necessarily distinct). For every ticket, look backward (toward earlier tickets in the queue) and find the nearest earlier ticket whose printed value is strictly greater than the current ticket's value. Report that value, or -1 if no earlier ticket has a strictly greater value.
Line 1: an integer n.
Line 2: n space-separated integers, the ticket values in issue order.
n space-separated integers on one line: for each ticket (in issue order), the value of the nearest earlier strictly-greater ticket, or -1.
Example 1
Input
5 5 3 4 2 6
Expected
-1 5 5 4 -1
Explanation
Ticket 0 (5) has nothing before it: -1. Ticket 1 (3): nearest earlier greater is 5. Ticket 2 (4): nearest earlier greater is 5 (3 is not greater). Ticket 3 (2): nearest earlier greater is 4. Ticket 4 (6): no earlier ticket is greater than 6: -1.
Example 2
Input
3 1 2 3
Expected
-1 -1 -1
Explanation
Values strictly increase, so no ticket ever has a strictly greater ticket before it.
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 →