Challenge: Randomized Treap

Start with the idea

Solve the exact task, not just the visible example: Apply the insert/delete operations and return keys requested by inorder. On input insert5 insert2 insert8 insert1 delete2 inorder, predict the output before opening the answer reveal. The revealed output is a test oracle for this case, while private checks exercise other legal cases. Start by stating the input grammar and output format in your own words. Parse the complete input, including surrounding whitespace, before relying on any convenient positions in the example.

Build the solution around one maintained claim: Keep BST order by key and heap order by random priority; split and merge preserve both. Decide what state represents that claim, how it is initialized, what a single update does, and when the algorithm stops. An advanced structure or offline query order packages an invariant across operations. Name what each node, block, or reordered query state stores. Trace the visible input by hand and record at least two intermediate states, not only the final answer. If the trace cannot justify your predicted output, there is a gap between the idea and the implementation.

Use the Rust sketch as a guide, not a substitute for a complete solve function. The supplied Rust sketch is an invariant note rather than a complete program. Turn it into explicit state and transitions before coding. Keep representation and operations separate in Rust. Verify a tiny instance against a straightforward reference implementation before optimizing.