Preimages under the Queuesort algorithm

Queuesort is an algorithm which tries to sort an input permutation π by using a queue. Similarly to what has been done for Stacksort (more recently by Defant and less recently by Bousquet-Mélou), we study preimages of permutations under Queuesort. Characterization of preimages. Alternative way of describing the output q(π) of Queuesort on input π. Recursive characterization of preimages of a given permutation, from which we deduce a recursive procedure to generate them. Enumeration of preimages. Enumeration of q^{−1} (M_1 P_1 M_2), where M_1, M_2 are all the maximal sequences of LTR maxima of π (with M_2 possibly empty): combinations of Catalan numbers. Catalan numbers when |M_2| = 1. Enumeration of permutations with one preimage: derangement numbers.