== include(page="template/taskheader" task_id="seriale") ==
Poveste şi cerinţă...
Plictisit pana peste cap de facultate, Bossanip s-a apucat sa se uite la seriale. El are atat de multe de vazut incat nici nu mai stie in ce ordine sa le vizioneze. Dupa multe zile de cercetare a ajuns la urmatorul algoritm de vizionare a serialelor: Initial, acesta asociaza fiecarul serial un indice natural distinct. Cu cat indicele serialului este mai mare, cu atat serialul este mai bun. La urmatorul pas a impartit serialele in $2$ liste: o lista cu $N$ seriale si o lista cu $K$ seriale (in total avem $N + K$ seriale, fiecare avand un indice diferit din intervalul $[1, N + K]$). Deoarece nu vrea sa se uite la seriale de la cele mai bune la cele mai slabe sau invers (ca s-ar plictisi pe final, respectiv la inceput), el s-a hotarat sa selecteze din prima lista o data cel mai bun serial, dupa cel mai slab serial, dupa din nou cel mai bun si din nou cel mai slab etc. De fiecare data cand selecteaza un serial din prima lista, acesta selecteaza un serial din lista $2$ (pe care vrea el) si il introduce in lista $1$ (unde vrea el). Astfel, la fiecare moment de timp in lista $1$ sunt $N$ seriale.
Acum Bossanip va fi putin penal. El observa ca de fiecare data cand selecteaza cel mai mare/cel mai mic element, trebuie sa itereze prin toata lista de lungime $N$ si sa stearga elementul de acolo (deoarece initial el are o lista cu serialele doar ca intr-o ordine aleatoare). Lenes de fire, el ar vrea ca cel mai mic element sa fie mereu in stanga si cel mai mare element in dreapta. Ca sa fie sigur ca totul e bine, ar prefera sa sorteze lista. Bossanip nu stie nici un algoritm de sortare, dar stie treapuri si poate foarte usor sa scoata un element din lista si sa introduca alt element unde vrea el.
Deoarece Bossanip nu are viziune asupra lumii, perspectiva narativa sau nici un fel de profunzime matematica, el va roaga pe voi sa aflati numarul minim de pasi(sau dupa cate seriale) o sa poata sa aibe lista sortata. Practic trebuie sa gasiti o strategie pentru alegerea serialelor din lista $2$ si a pozitiilor unde vor fi inserate, astfel incat lista $1$ sa devina sortata cat mai devreme.
h2. Date de intrare
Fişierul de intrare $seriale.in$ ...
Fişierul de intrare $seriale.in$ va contine pe prima linie $2$ numere naturale $N$ si $K$. Pe linia $2$ vor fi $N$ numere reprezentand indicii serialelor din prima grupa. Pe linia $3$ vor fi $K$ numere reprezentand indicii serialelor din grupa $2$.
h2. Date de ieşire
În fişierul de ieşire $seriale.out$ ...
Fişierul de ieşire $seriale.out$ va contine un singur numar natural reprezentand numarul minim de pasi necesari sa sortezi prima lista sau $-1$ daca nu se poate in $K$ operatii. Dupa ce a vizionat $K$ seriale si lista $2$ devine goala, Bossanip se opreste. In caz ca lista $1$ nu a devenit sortata, acesta considera ca nu si-a atins scopul (si desigur afiseaza $-1$).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ K ≤ 200.000$
* Valorile din cele doua liste sunt numere naturale distincte din intervalul $[1, N + K]$
* Pentru $10%$ din teste $N, K ≤ 8$
* Pentru $30%$ din teste $N, K ≤ 100$
* Pentru $60%$ din teste $N, K ≤ 4000$
h2. Exemplu
table(example). |_. seriale.in |_. seriale.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 5
3 1 5 2 4
6 8 7 9 10
|4
|
h3. Explicaţie
...
La primul pas Bossanip o sa se uite la cel mai bun serial din prima lista (cel cu indicele $5$) si o sa introduca serialul $7$ in capatul listei. Lista o sa arate: $3 1 2 4 7$. La pasul $2$ o sa se uite la $1$ si intra $8$ (lista va fi $3 2 4 7 8$). La pasul $3$, $9$ o sa intre in locul lui $8$. Dupa pasul $4$ (ultimul pas), $2$ o sa fie eliminat, intra $10$ in capat si lista va fi $3 4 7 9 10$ (care este sortata).
== include(page="template/taskfooter" task_id="seriale") ==
