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

Se considera o lista simplu inlantuita ({$L1$}) ce contine numerele intregi de la $1$ la $N$ (intr-o ordine oarecare). Se doreste construirea unei alte liste simplu inlantuite ({$L2$}) care sa contina numerele din lista $L1$ in ordine crescatoare. Pentru a obtine lista L2, se vor sterge elemente din $L1$ si se vor adauga in $L2$, conform procedeului descris in continuare: initial lista L2 e vida. La primul pas putem sterge orice element din $L1$ si acesta se adauga in $L2$. Apoi, in urmatorii $N-1$ pasi, se poate sterge orice element din $L1$, dar acesta poate fi adaugat numai la inceputul sau la sfarsitul lui $L2$. La final, $L1$ nu va contine nici un element, iar $L2$ trebuie sa contina numerele de la $1$ la $N$ in ordine crescatoare. Intrucat exista mai multe posibilitati de a construi $L2$, vom defini in continuare costul constructiei lui $L2$ si vom dori sa determinam o posibilitate de constructie a lui $L2$ care sa aiba costul minim.

Se considera o lista simplu inlantuita ({$L1$}) ce contine numerele intregi de la $1$ la $N$ (intr-o ordine oarecare). Se doreste construirea unei alte liste simplu inlantuite ({$L2$}) care sa contina numerele din lista $L1$ in ordine crescatoare. Pentru a obtine lista $L2$, se vor sterge elemente din $L1$ si se vor adauga in $L2$, conform procedeului descris in continuare: initial lista $L2$ e vida. La primul pas putem sterge orice element din $L1$ si acesta se adauga in $L2$. Apoi, in urmatorii $N-1$ pasi, se poate sterge orice element din $L1$, dar acesta poate fi adaugat numai la inceputul sau la sfarsitul lui $L2$. La final, $L1$ nu va contine nici un element, iar $L2$ trebuie sa contina numerele de la $1$ la $N$ in ordine crescatoare. Intrucat exista mai multe posibilitati de a construi $L2$, vom defini in continuare costul constructiei lui $L2$ si vom dori sa determinam o posibilitate de constructie a lui $L2$ care sa aiba costul minim.

Algoritmul de constructie a lui $L2$ consta din $N$ pasi, la fiecare pas stergandu-se un element din $L1$ si adaugand acest element in $L2$ (conform restrictiilor precizate). La pasul $i$ ({$1 ≤ i ≤ N$}), lista $L1$ contine $N-i+1$ elemente si lista $L2$ contine $i-1$ elemente. Daca se muta elementul de pe pozitia $k$ din $L1$ in $L2$ la pasul $i$ ({$1 ≤ k ≤ N-i+1$}), costul acestei mutari este egal cu ${*k*i*}$. Dupa mutarea elementului, lista $L1$ va avea cu un element mai putin (toate elementele de pe pozitii mai mari decat $k$ vor ajunge cu o pozitie mai in fata) si lista $L2$ va avea cu un element mai mult. Costul total al constructiei lui $L2$ este egal cu suma costurilor mutarilor efectuate la fiecare dintre cei $N$ pasi.