Перестановки#5304
Саша та Федя грають у цікаву гру. У них є кубиків, на яких написані різні числа від до . Хлопчики намалювали на папері клітинок у ряд і грають за наступними правилами.
Спочатку перший гравець виставляє деякі кубики на клітинки, потім другий гравець виставляє на вільні клітинки кубики, що залишилися. Після цього перший гравець робить наступні дії: він дивиться, яке число написано на останньому кубику (нехай це число ) і після цього переставляє останні кубиків у зворотному порядку. Ці дії перший гравець повторює до тих пір, доки останнім не стане кубик з числом .
Наприклад, нехай у хлопців п'ять кубиків. Якщо перший гравець поставив другий і третій кубики на третє та п'яте місце: «..3.2», то другий гравець може розставити кубики, що залишилися, так: «41352». У цьому випадку першому гравцеві потрібно зробити п'ять дій: «41325», «52314», «54132», «54123», «54321», після чого гра завершиться.
Саша зробив перший хід. Допоможіть Феді розставити кубики так, щоб Саша зробив максимально можливу кількість дій.
У першому рядку міститься число (1 \leq n \leq 25). У наступних числах задається розміщення кубиків після ходу Саші. Число означає, що клітинка вільна, число від до — номер кубика, який стоїть у цій клітинці. У вхідному файлі не більше нулів.
У першому рядку вихідного файлу виведіть максимальну кількість дій, яку доведеться зробити Саші. У другому рядку виведіть чисел від до , де -те число означає номер кубика, який стоїть у -ій клітинці після ходу Феді. Якщо оптимальних розв'язків декілька, виведіть довільний із них.
Приклад 1