Is anything known about the following?
I hold in my hand a shuffled pack of cards numbered 1$1$ to n$n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, say card numbered k$k$, I open a new pile only if the top card of an existing pile is not k + 1;$k + 1$; otherwise I place that card on top of that pile. If at any stage (before dealing a new card) the bottom card of an existing pile is one less than the top card of another pile, I combine the two into a new pile in the obvious way.
What is the most likely maximum number of piles that will be formed at some stage while so dealing the n$n$ cards?
What is the expected maximum number of piles that will be formed at some stage while so dealing the n$n$ cards?
In both cases, count piles only if no two piles can be combined into one.