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

**Spoiler alert!** Dupa moartea lui Miclovan viata a devenit monotona si absenta, comisarul Roman este pus in situatia de a il prinde pe Semaca, pe care justitia l-a achitat din lipsa de probe.

**Spoiler alert!** Dupa moartea lui Miclovan viata a devenit monotona si absenta, comisarul fiind Roman este pus in situatia de a il prinde pe Semaca, anticarul proaspat achitat de justitie din lipsa de probe.

Astfel, Roman ajunge in fata unei arhive vechi, plina cu $N$ dosare ({$N$} putere a lui {$2$}), aranjate intr-o ordine aleatorie. Un prim pas in analizarea acestora il reprezinta ordonarea lor alfabetica dupa titlu. Vom considera, pentru simplitate, ca titlurile celor $N$ dosare sunt numere naturale distincte, cuprinse intre $1$ si $N$ (altfel spus, ordinea dosarelor reprezinta o permutare a numerelor de la $1$ la $N$). Deoarece numarul dosarelor este destul de mare, Roman propune o abordare sistematica, pe care o va duce la bun sfarsit cu ajutorul subordonatilor sai. Aceasta poate fi descrisa prin urmatorul algoritm:

Astfel, Roman ajunge in fata unei arhive vechi, plina cu $N$ dosare ($N$ putere a lui $2$), aranjate intr-o ordine aleatorie. Un prim pas in analizarea acestora il reprezinta ordonarea lor alfabetica dupa titlu. Vom considera pentru simplitate ca titlurile celor $N$ dosare sunt numere naturale distincte, cuprinse intre $1$ si $N$ (altfel spus, ordinea dosarelor reprezinta o permutare a numerelor de la $1$ la $N$). Deoarece numarul dosarelor este destul de mare, Roman propune o abordare sistematica, pe care o va duce la bun sfarsit cu ajutorul subordonatilor sai. Aceasta poate fi descrisa prin urmatorul algoritm:

== code(cpp) |
const int NMAX = 1000000000;

}
==

Mai exact, procedura lui Roman este reprezentata de un singur apel al procedurii $bubblesort()$.
Dupa rapida ordonare a dosarelor, Roman isi pune o intrebare existentiala "Care e valoarea maxima a variabilei $ops$ pentru o permutare oarecare?"

Mai exact, procedura lui Roman este un singur apel al functiei $bubblesort()$.
Dupa imediata ordonare a dosarelor Roman isi pune o intrebare existentiala "Care e cea mai mare valoare posibila a variabilei $ops$ pentru o permutare oarecare?"

h2. Cerinta
Dandu-se $N$, numar natural nenul, putere a lui 2, sa se calculeze urmatoarele

# Valoarea maxima a variabilei $ops$ dupa un apel al procedurii $bubblesort()$;

# Valoarea maxima posibila a variabilei $ops$ dupa un singur apel al functiei $bubblesort()$;

# Numarul de permutari cu $N$ elemente pentru care se atinge acest maxim;

# Dintre acestea, permutarea minima din punct de vedere lexicografic. Deoarece output-ul ar fi prea mare, se va da un un sir cu $M$ elemente $a{~i~}$ si se va cere pentru fiecare element $a{~i~}$ sa se afiseze valoarea $p[a{~i~}]$.

# Dintre acestea, permutarea minima din punct de vedere lexicografic. Deoarece output-ul poate fi prea mare, se va da un un sir cu $M$ elemente $a{~i~}$ si se va cere pentru fiecare element $a{~i~}$ sa se afiseze valoarea $p[a{~i~}]$.

h2. Date de intrare