Fișierul intrare/ieșire	mediana.in, mediana.out	Sursă	Concurs IQ Academy | Clasa a 10-a
Autor	din folclor	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.2 sec	Limită de memorie	3072 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Mediana (clasa a 10-a)

Numim mediana unui vector cu N elemente valoarea care se află pe poziția (N + 1) / 2 după sortarea elementelor în ordine crescătoare.

Cerință

Avem un vector care este inițial gol. Se dau Q operații de forma:

• 1 X: adăugați numărul X în vector
• 2: afișați mediana vectorului

Date de intrare

Fișierul de intrare mediana.in conține pe prima linie numărul natural Q, iar pe următoarele Q linii operațiile descrise în enunț.

Date de ieșire

În fișierul de ieșire mediana.out se vor găsi răspunsurile operațiilor de tip 2, fiecare răspuns pe câte o linie.

Restricții

• 1 ≤ Q ≤ 100.000
• 1 ≤ X ≤ 10⁹
• Se garantează că prima operație nu este de tip 2.

Exemplu

Explicație

Pentru prima întrebare, vectorul este {2, 3, 1, 4, 5}. Îl vom ordona crescător: {1, 2, 3, 4, 5}. Deci mediana este 3.
Pentru cea de-a doua întrebare, vectorul ordonat crescător este {1, 2, 3, 4, 5, 6, 7, 8}. Deci mediana este 4.