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

Se da o colectie de numere naturale initial vida. Se cere sa se efectueze $N$ operatii asupra acestei multimi astfel:

Se da o colectie de numere naturale initial vida. Se cere sa se efectueze $N$ operatii asupra acestei multimi, astfel:

* Operatia de tipul 1: insereaza elementul $x$ in colectie
* Operatia de tipul 2: sterge elementul $NRI[x]$, unde $NRI[x]$ este al $X$-lea element intrat in colectie.
* Operatia de tipul 3: afisarea elementului minim din colectie
 
Se garanteaza ca nu se vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din colectie.

* Operatia de tipul 1: se insereaza elementul $x$ in colectie
* Operatia de tipul 2: se sterge al $x$-lea element intrat in colectie in ordine cronologica
* Operatia de tipul 3: se afiseaza elementului minim din colectie

h2. Date de intrare

Fisierul de intrare $heapuri.in$ va contine pe prima linie numarul $N$. Pe liniile $2$ .. $N+1$ se va afla descrierea operatiilor care trebuie efectuate. Primul numar, $cod$, reprezinta tipul operatiei care urmeaza a fi efectuata. Daca $cod$ este $1$ sau $2$ atunci se va mai citi si numarul $x$ avand semnificatia din enunt.

Fisierul de intrare $heapuri.in$ va contine pe prima linie numarul $N$. Pe liniile $2$ .. $N+1$, se va afla descrierea operatiilor care trebuie efectuate. Primul numar, $cod$, reprezinta tipul operatiei. Daca $cod$ este $1$ sau $2$, atunci se va mai citi si numarul $x$, avand semnificatia din enunt.

h2. Date de ieşire

Fisierul de iesire $heapuri.out$ va contine pe cate o linie raspunsul pentru fiecare operatie de tipul $3$ din fisierul de intrare.

Fisierul de iesire $heapuri.out$ va contine pe cate o linie raspunsul pentru fiecare operatie de tipul $3$ din fisierul de intrare in ordinea data.

h2. Restricţii
* $1 ≤ N ≤ 200 000$
* Elementele colectiei nu vor depasi $1 000 000 000$
* Se garanteaza ca nu se va cere niciodata sa se afle minimul daca colectia este vida

* Se garanteaza ca nu se vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din colectie.

h2. Exemplu

h2. Indicatii de rezolvare

Problema se poate rezolva brut-force tinand numerele intrun vector, si efectuand pur si simplu fiecare operatie. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte si nu ar trebui sa ia $~30$ de puncte.

Problema se poate rezolva $brute-force$, tinand numerele intr-un vector si efectuand fiecare operatie fara nici un rafinament. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte. O astfel de rezolvare nu ar trebui sa ia mai mult de $30$ de puncte.

Rezolvarea optima bazeaza pe folosirea unui heap, care suporta aceste efectuarea operatiilor de tipul $1$ si $2$ in $O(log N)$ si a operatiilor de tipul $3$ in $O(1)$.
Un heap este un arbore binar, cu proprietatea ca fiecare nod, are asociata o cheie, cheie care este mica decat cheile asociate nodurilor din subarborele sau. Evident raspunsul la operatiile de tip $3$ se va gasi in radacina arborelui.