Before revision:  Previously such a separation was known only for k = 2. We stress that for k= 2 , there are only finitely many distinct problems to consider.
After revision:  We also extend previously known results in the insertion-only setting to a wide variety of cases, and in particular the case of k = 2. We stress that for k= 2 , there are only finitely many distinct problems to consider.