Eccoci.

Consider the following algorithm for sorting a list:

• 1. Starting from the beginning of the list, check each pair of adjacent elements in turn.
• 2. If the elements are out of order:
  • a. Move the smallest element of the pair at the beginning of the list.
  • b. Restart the process from step 1.
• 3. If all pairs are in order, stop.

For example, the list $\{\,4\,1\,3\,2\,\}$ is sorted as follows:

• $\underline{4\,1}\,3\,2$ ($4$ and $1$ are out of order so move $1$ to the front of the list)
• $1\,\underline{4\,3}\,2$ ($4$ and $3$ are out of order so move $3$ to the front of the list)
• $\underline{3\,1}\,4\,2$ ($3$ and $1$ are out of order so move $1$ to the front of the list)
• $1\,3\,\underline{4\,2}$ ($4$ and $2$ are out of order so move $2$ to the front of the list)
• $\underline{2\,1}\,3\,4$ ($2$ and $1$ are out of order so move $1$ to the front of the list)
• $1\,2\,3\,4$ (The list is now sorted)

Let $F(L)$ be the number of times step 2a is executed to sort list $L$. For example, $F(\{\,4\,1\,3\,2\,\}) = 5$.

We can list all permutations $P$ of the integers $\{1, 2, \dots, n\}$ in lexicographical order, and assign to each permutation an index $I_n(P)$ from $1$ to $n!$ corresponding to its position in the list.

Let $Q(n, k) = \min(I_n(P))$ for $F(P) = k$, the index of the first permutation requiring exactly $k$ steps to sort with First Sort. If there is no permutation for which $F(P) = k$, then $Q(n, k)$ is undefined.

For $n = 4$ we have:

Let $R(k) = \min(Q(n, k))$ over all $n$ for which $Q(n, k)$ is defined.

Find $R(12^{12})$.