Chef Feeds Cats

Chef owns $N$ cats (numbered $1$ through $N$) and he wants to feed them. There are $M$ identical cans of cat food; each can must be used to feed exactly one cat and Chef can only feed one cat at a time. Chef wrote down the order in which he wants to feed the cats: a sequence $A_1, A_2, \ldots, A_M$. An order of feeding cats is *fair* if there is no moment where Chef feeds a cat that has already b