2-3-4 Tree: root after insertions

2-3-4 Tree: the root after insertions

Insert the given distinct integers in input order into an initially empty 2-3-4 tree using the top-down "split on the way down" strategy, then print the root node's keys.

Top-down insertion:

1. If the root is a 4-node (3 keys), split the root first: the middle key becomes the new root and the tree grows one level.
2. Descend from the root; whenever the child you are about to enter is a 4-node, split it first (middle key promoted to the parent), then continue.
3. At the leaf, insert the value in sorted order.

This is the COMP2521 21T3 Q3 style "what is the root after inserting" question. Complete splitChild and insert.

Input

• Line 1: integer n (count, may be 0).
• Line 2: n distinct integers, inserted in this order.

Output

• One line: the final root node's keys ascending, a space after each value. Empty line if n = 0.

Example: input 7 / 10 20 30 40 50 60 70 -> 20 40 .