Permutasiyalar
Sasha və Fedya maraqlı bir oyun oynayırlar. Onların n ədəd kubikləri var və hər bir kubikin üzərində 1-dən n-ə qədər müxtəlif rəqəmlər yazılıb. Oğlanlar kağız üzərində n hüceyrədən ibarət bir sıra çəkiblər və oyunu aşağıdakı qaydalarla oynayırlar.
Əvvəlcə birinci oyunçu bəzi kubikləri hüceyrələrə yerləşdirir, sonra ikinci oyunçu qalan kubikləri boş hüceyrələrə yerləşdirir. Bundan sonra birinci oyunçu aşağıdakı hərəkətləri edir: o, sonuncu kubikdə hansı rəqəmin yazıldığını (bu rəqəm a olsun) baxır və sonra sonuncu a kubikləri tərsinə çevirir. Bu hərəkətləri birinci oyunçu sonuncu kubikdə 1 rəqəmi olana qədər təkrar edir.
Məsələn, oğlanların beş kubiki olsun. Əgər birinci oyunçu ikinci və üçüncü kubikləri üçüncü və beşinci yerə yerləşdiribsə: "..3.2", ikinci oyunçu qalan kubikləri belə yerləşdirə bilər: "41352". Bu halda birinci oyunçu beş hərəkət etməlidir: "41325", "52314", "54132", "54123", "54321", sonra oyun bitəcək.
İndi ilk gedişi Sasha etdi. Fedya'ya kubikləri elə yerləşdirməyə kömək edin ki, Sasha mümkün olan maksimum sayda hərəkət etsin.
Giriş verilənləri
Giriş faylında n (1 ≤ n ≤ 25) ədədi var. Növbəti n ədəd Sasha'nın gedişindən sonra kubiklərin yerləşməsini göstərir. 0 ədədi hüceyrənin boş olduğunu, 1-dən n-ə qədər olan ədəd isə həmin hüceyrədə duran kubikin nömrəsini göstərir. Giriş faylında ən çox 10 sıfır var.
Çıxış verilənləri
Çıxış faylının birinci sətrində Sasha'nın etməli olduğu maksimum hərəkət sayını göstərin. İkinci sətrdə n ədəd 1-dən n-ə qədər olan ədədləri göstərin, burada i-ci ədəd Fedya'nın gedişindən sonra i-ci hüceyrədə duran kubikin nömrəsini göstərir. Əgər optimal həllər bir neçədirsə, istənilən birini göstərin.