Suppose that I have a deck of $n$ cards numbered $1$ to $n$. I randomly draw the cards from the deck one by one and put them in piles according to the following rule:
The first drawn card forms the first pile.
For each subsequent card drawn, if the number on it is just smaller than the smallest number on cards in an existing pile by one, or just larger than the largest number on cards in an existing pile by one, then I will put this card on that pile.
If a newly drawn card cannot be put in any existing piles according to rule 2, then start a new pile with this card.
For example, if $n=6$ and the order of the cards drawn is $(2,5,1,3,6,4)$, then the piles of cards will be (step by step)
$(2)$
$(2), (5)$
$(12), (5)$
$(123), (5)$
$(123), (56)$
$(123), (456)$ or $(1234), (56)$
and I will have 2 piles.
My question is how to find the expected number of piles, $k$, I will get. My guess is $E[k] = (n+1)/3$.