== 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 il prinde pe Semaca, pe care justitia l-a achitat 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:
 

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

int n;
int p[NMAX + 1];

int N;
int p[NMAX + 1]; // = permutarea data

int ops;
void bubble(int gap) {
    bool ok = true;
    while (ok) {
        ok = false;

        for (int i = 1; i <= n - gap; ++ i)

        for (int i = 1; i <= N - gap; ++ i)

            if (p[i] > p[i + gap]) {
                swap(p[i], p[i + gap]);
                ++ ops;

}
void bubblesort() {

    int gap = n;

    int gap = N;

    while (gap) {
        bubble(gap);
        gap /= 2;