Cartesian Tree Facts

A treap is exactly a Cartesian tree whose second coordinate is a random priority.

The dual invariant forces $O(\log n)$ depth on any input, which is why no rebalancing is needed.

It builds in $O(n)$ with a monotonic stack, because each element enters and leaves the right spine at most once.

Every subtree spans a contiguous range of the original array.

The array must be sorted first, so construction is $O(n \log n)$.