Sleepy Cow Sorting

Farmer John has N cows labeled \(1,2,\dots,N\) arranged in a line in the order \(p_1,p_2,\dots,p_N\). He stands in front of cow \(p_1\). He wishes to reorder the cows so that they are in increasing order \(1,2,\dots,N\) with cow 1 standing next to him.

The cows are rather sleepy today so at any moment only the cow at the very front of the line (the one facing Farmer John) is paying attention. In one move, Farmer John can instruct the front cow to move \(k\) steps toward the back of the line where \(1 \le k \le N-1\). When she moves, she passes over exactly \(k\) cows; those cows all shift one position forward to fill the gap, and the instructed cow inserts herself immediately after them.

For example, if \(N=4\) and the cows start in the order below (with FJ at the front):

FJ: 4 3 2 1

If FJ instructs cow 4 (the only one listening) to move \(2\) steps, then the cow will pass cows 3 and 2, and the new order becomes:

FJ: 3 2 4 1

Now cow 3 is at the front and will be the only one who listens to the next command. Farmer John wants to achieve the final sorted order \(1,2,3,4\) using the minimum possible number of moves. Help him by providing a sequence of moves (i.e. the \(k\) values for each operation) that sorts the cows in minimum moves.

Note (with \(\LaTeX\)): It can be shown that the minimum number of moves required is equal to \(m\), where if the longest increasing suffix of the permutation (when read from the end) starts at position \(m+1\), then the answer is \(m\). Moreover, an optimal strategy is to not move the cows in this sorted suffix. For the cows that are moved (say in a set \(A\)) in the order they originally appear, one valid strategy is to process them in reverse order and determine an insertion index via binary search into the already fixed sorted suffix. Specifically, if we denote by \(B\) the longest increasing suffix and by \(A\) the remaining prefix, then for each cow \(x\) in \(A\), processed in reverse order, let \(\text{pos}\) be the insertion position in \(B\) (maintained in sorted order) such that all cows before \(\text{pos}\) are less than \(x\). Then a valid move is to instruct the cow to move \(\text{pos}+1\) steps. Reversing the order of these moves gives an optimal sequence.

inputFormat

The first line contains an integer \(N\) \( (1 \le N \le 10^5)\), the number of cows. The second line contains \(N\) distinct integers \(p_1, p_2, \dots, p_N\) representing the initial ordering from front to back.

outputFormat

On the first line, output the minimum number of moves \(M\) needed. If \(M > 0\), then output \(M\) more lines, each containing a single integer representing the value \(k\) (the number of cows the front cow should move over) for that move. It is guaranteed that following these moves will sort the cows in increasing order.

sample

4
4 3 2 1

3
3
2
1