Stack Permutation Algorithm
Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are equivalent problems because if we choose a prefix $\sigma(1)\sigma(2)\ldots \sigma(i)$ and right-cycle it, then we can reverse that by choosing the $\sigma(i)$ (now the leftmost point) and inserting it at position $i$. Likewise rather than start from the identity, we end at the identity.

Let $\sigma(i^*)$ be the right most element that is the beginning of an inversion, i.e., there exists $j&gt;i^*$ with $\sigma(i^*)&gt;\sigma(j)$ (if none exists then no moves are necessary because $\sigma$ is the identity permutation). For instance in 1 3 2 4 that would be 3 since it starts the inversion (3,2). And in 4 3 2 1 that would be 2.

Observation 1:  $\sigma(i^*+1)\sigma(i^*+2)\cdots \sigma(n)$ is sorted.

We must move all elements on the left side of $\sigma(i^*)$ to the right side of $\sigma(i^*)$. This is because we must correct the inversion and that can't happen until we perform a move with $\sigma(i^*)$ itself, which can't happen until $\sigma(i^*)$ is "uncovered" on the left side. While performing these hops over $\sigma(i^*)$ we can maintain the invariant that everything to the right of $\sigma(i^*)$ is sorted; this is just insertion into a sorted array.

So the number of moves necessary $= i^*$, since we hop everything to the left of $\sigma(i^*)$, and lastly move $\sigma(i^*)$ to its correct index.

Concluding note: to actually find the indices, we could use an order-statistic tree initialized with all values to the right of $\sigma(i^*)$. When we jump $\sigma(1)$ over $\sigma(i^*)$ we insert $\sigma(1)$ into the tree and call rank($\sigma(1)$); the rank can be used to compute the insertion index. Repeat with $\sigma(2), \ldots$.