Задача №1774. Перестановки
Саша и Федя играют в интересную игру. У них есть \(n\) кубиков, на которых написаны различные числа от 1 до \(n\). Ребята нарисовали на бумаге \(n\) клеточек в ряд и играют по следующим правилам.
Сначала первый игрок выставляет некоторые кубики на клеточки, затем второй игрок выставляет на свободные клетки оставшиеся кубики. После этого первый игрок делает следующие действия: он смотрит, какое число написано на последнем кубике (пусть это число a) и после этого переставляет последние a кубиков в обратном порядке. Эти действия первый игрок повторяет до тех пор, пока последним не станет кубик с числом 1.
Например, пусть у ребят пять кубиков. Если первый игрок поставил второй и третий кубик на третье и пятое место: «..3.2», то второй игрок может расставить оставшиеся кубики так: «41352». В этом случае первому игроку потребуется сделать пять действий: «41325», «52314», «54132», «54123», «54321», после чего игра закончится.
Сейчас первым ходил Саша. Помогите Феде расставить кубики так, чтобы Саша сделал максимально возможное количество действий.
Во входном файле содержится число \(n\) (1 ≤ \(n\) ≤ 25). Следующие \(n\) чисел задают расположение кубиков после хода Саши. Число 0 означает, что клетка свободна, число от 1 до \(n\) – номер кубика, который стоит в этой клетке. Во входном файле не более 10 нулей.
На первой строке выходного файла выведите максимальное количество действий, которое придется сделать Саше.
На второй строке выведите \(n\) чисел от 1 до \(n\), где \(i\)-е число означает номер кубика, стоящего в \(i\)-ой клетке после хода Феди. Если оптимальных решений несколько, выведите любое.
3 0 0 0
2 2 1 3
4 0 0 0 0
4 2 4 1 3