3. [10 marks] Prove the following statement: Starting from an empty splay tree, there ex- ists a sequence of n insertions such that, after all these insertions have been performed the height of the splay tree becomes (n). In your solution, carefully prove why the sequence you come up with indeed makes the height of the splay tree be (n)