Рассмотрим следующий алгоритм сортировки списка чисел по возрастанию:

• 1. Последовательно проверить каждую пару соседних элементов, начиная с первых двух.
• 2. Если элементы пары расположены в неправильном порядке:
  • a. Переместить меньший элемент пары в начало списка.
  • b. Начать снова с шага 1.
• 3. Если все пары имеют правильный порядок, остановиться.

Например, список { 4 1 3 2 } будет отсортирован следующим образом:

• 4 1 3 2 (4 и 1 в неправильном порядке, 1 перемещается в начало списка)
• 1 4 3 2 (4 и 3 в неправильном порядке, 3 перемещается в начало списка)
• 3 1 4 2 (3 и 1 в неправильном порядке, 1 перемещается в начало списка)
• 1 3 4 2 (4 и 2 в неправильном порядке, 2 перемещается в начало списка)
• 2 1 3 4 (2 и 1 в неправильном порядке, 1 перемещается в начало списка)
• 1 2 3 4 (список отсортирован)

Пусть F(L) будет количеством исполнений шага 2a в процессе сортировки списка L. Например, F({ 4 1 3 2 }) = 5.

Мы можем перечислить все перестановки P целых чисел {1, 2, ..., n} в лексикографическом порядке и присвоить каждой перестановке индекс I_n(P) от 1 до n!, соответствующий ее положению в получившемся списке.

Пусть Q(n, k) = min(I_n(P)) для F(P) = k будет индексом первой перестановки, требующей ровно k шагов для сортировки списка алгоритмом "первая сортировка". Если не существует такой перестановки, для которой F(P) = k, то значение Q(n, k) не определено.

Для n = 4 имеем:

Пусть R(k) = min(Q(n, k)) для всех n, для которых значение Q(n, k) определено.

Найдите R(12¹²).