Let T be an arbitrary splay tree storing n elements A 1 , A 2 , . A n , where A 1 ≤ A 2 ≤ . . . ≤ A n . We perform n search operations in T, and the ith search operation looks for element A i . That...

Let T be an arbitrary splay tree storing n elements A₁, A₂, . A_n, where A₁ ≤ A₂ ≤ . . . ≤ A_n.

We perform n search operations in T, and the ith search operation looks for element A_i. That is, we search for items A₁, A_2
, . . . , A_n one by one.

What will T look like after all these n operations are performed? For example, what will the shape of the tree be like? Which node stores A₁, which node stores A₂, etc.?

Prove the answer you gave for formally. Your proof should work no matter what the shape of T was like before these operations.