Permutasiyalar#5304
Sasha və Fedya maraqlı bir oyun oynayırlar. Onların ədəd kubikləri var və hər bir kubikin üzərində -dən -ə qədər müxtəlif rəqəmlər yazılıb. Oğlanlar kağız üzərində 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 olsun) baxır və sonra sonuncu kubikləri tərsinə çevirir. Bu hərəkətləri birinci oyunçu sonuncu kubikdə 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. Fedyaya kubikləri elə yerləşdirməyə kömək edin ki, Sasha mümkün olan maksimum sayda hərəkət etsin.
Giriş faylında (1 \leq n \leq 25) ədədi var. Növbəti ədəd Sashanın gedişindən sonra kubiklərin yerləşməsini göstərir. ədədi hüceyrənin boş olduğunu, -də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 sıfır var.
Çıxış faylının birinci sətirində Sashanın etməli olduğu maksimum hərəkət sayını göstərin. İkinci sətirdə ədəd -dən -ə qədər olan ədədləri göstərin, burada -ci ədəd Fedyadan sonra -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.
Nümunə 1