Suppose we insert $$ elements $1,...,$ one after the other, into an initially$-$empty treap. Prove that

the expected number of times that the root of the treap changes during the entire sequence of

insertions is $($log $)$