A warehouse conveyor feeds numbered cargo crates one at a time toward two collection chutes, A and B. The very first crate to arrive is always routed to chute A, and the second crate is always routed to chute B. Every crate after that is routed by a simple rule: compare the value of the crate most recently placed into chute A against the value of the crate most recently placed into chute B; if chute A's most recent value is strictly greater, the new crate is routed to chute A, otherwise it is routed to chute B. Once every crate has been routed, report the final combined sequence formed by listing every crate now in chute A in the order it arrived, followed by every crate now in chute B in the order it arrived.
n, the number of crates.n space-separated integers, the crate values in arrival order.Print the n crate values of the combined sequence (chute A's crates in arrival order, then chute B's crates in arrival order), space-separated on one line.
Example 1
Input
5 7 3 9 1 5
Expected
7 9 1 3 5
Explanation
Crate 7 goes to A, crate 3 to B. Crate 9: A's last (7) > B's last (3), so 9 joins A -> A=[7,9]. Crate 1: A's last (9) > B's last (3), so 1 joins A -> A=[7,9,1]. Crate 5: A's last (1) is not greater than B's last (3), so 5 joins B -> B=[3,5]. Combined: A then B gives 7 9 1 3 5.
Example 2
Input
4 2 8 6 4
Expected
2 8 6 4
Explanation
Crate 2 goes to A, crate 8 to B. Crate 6: A's last (2) is not greater than B's last (8), so 6 joins B -> B=[8,6]. Crate 4: A's last (2) is still not greater than B's last (6), so 4 joins B -> B=[8,6,4]. Chute A never grows past its first crate, so the combined output is 2 8 6 4.
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 →