== include(page="template/taskheader" task_id="cheerleader") ==

Majoretele din şcoala lui Pătrăţel au hotărât să creeze o nouă manifestaţie artistică pentru cupa de Fo(1)tbal a şcolii. Sunt $2^N^$ majorete, fiecare cu înălţimi *distincte* între $0$ şi $2^N^ - 1$. Majoretele stau într-o linie. Înalţimea majoretei care este iniţial la pozitia $i$ este $h[i]$ pentru $1 ≤ i ≤ 2^N^$.

Poveste şi cerinţă...

Majoretele ştiu doua manevre sincronizate de dans:

h2. Date de intrare

* _Marele swap_. În manevra aceasta, primele $2^N-1^$ majorete fac schimb de locuri cu ultimele $2^N-1^$ majorete.
* _Marele split_. În manevra aceasta, majoretele situate la poziţii impare se duc la începutul rândului, si cele situate la poziţii pare se duc la sfârşitul rândului.

Fişierul de intrare $cheerleader.in$ ...

De exemplu, un _mare swap_ efectuat de majoretele $A, B, C, D, E, F, G, H$ va rezulta in randul $E, F, G, H, A, B, C, D$,  şi un _mare split_ efectuat de aceleasi majorete rezulta in randul $A, C, E, G, B, D, F, H$.

h2. Date de ieşire

Definim numărul de inversiuni ale unui rând de majorete cu înălţimile $h'&#91;1], ..., h'[2^N^]$ ca fiind numărul de perechi $(i, j), 1 &le; i < j &le; 2^N$ unde $h'[i] > h'[j]$. Majoretele vor să găsească o secvenţă de manevre care minimizeaza numărul de inversiuni ale rândului rezultant.

În fişierul de ieşire $cheerleader.out$ ...

h2. Fisier de intrare

h2. Restricţii

Pe prima linie a fisierului de intrare $cheerleader.in$ veţi găsi numărul întreg $N$.
Pe a doua linie a fisierului de intrare veţi găsi $2^N^$ numere întregi ce reprezintă $h[1], ..., h[2^N^]$.

* $... ≤ ... ≤ ...$

h2. Fisier de iesire
 
Pe primul rând al fisierului de iesire $cheerleader.out$ se va afla numărul minim de inversiuni.
Pe al doilea rând al outputului se va afla un şir de caractere ce reprezintă o secvenţă de manevre care conduce la numărul minim de inversiuni. Un caracter $1$ va reprezenta un _mare swap_, iar un caracter $2$ va reprezenta un _mare split_. Orice secvenţă de manevre care duce la numărul minim de inversiuni va fi acceptată.
 
h2. Restrictii
 
* $0 ≤ N ≤ 17$.
* $N$ poate fi 0.
* Lungimea secvenţei de manevre trebuie să fie de cel mult $500.000$.
* Pentru $16$ puncte, $N ≤ 4$
* Pentru $10$ puncte, $N ≤ 7$
* Pentru $25$ puncte, $N ≤ 11$
* Pentru $21$ puncte, $N ≤ 16$, se garantează că numărul minim de inversiuni ce poate fi obţinut este 0.
 
h2. Exemple

h2. Exemplu

table(example). |_. cheerleader.in |_. cheerleader.out |

|2
0 3 1 2
|1
2212
|
|3
2 3 7 6 1 4 5 0
|8
21221
|
|4
1 4 8 5 3 6 12 13 10 11 2 9 14 0 15 7
|43
2222
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
...

== include(page="template/taskfooter" task_id="cheerleader") ==