CMO 2012 Problem 5

A bookshelf contains $n$ volumes, labelled 1 to $n$, in some order. The librarian wishes to put them in the correct order as follows. The librarian selects a volume that is too far to the right, say the volume with label $k$, takes it out, and inserts it in the $k$-th position. For example, if the bookshelf contains the volumes $1,3,2,4$ in that order, the librarian could take out volume 2 and place it in the second position. The books will then be in the correct order 1, 2, 3, 4 .

(a) Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will eventually be in the correct order.

(b) What is the largest number of steps that this process can take?