Fişierul intrare/ieşire:costume.in, costume.outSursăBaraj Sumen 2013 juniori runda 2
AutorCatalin Francu, Victor ManzAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Costume

Un magazin de costume de Halloween a comandat N costume, toate diferite. Înainte de a plasa comanda, proprietarul a numerotat costumele în ordinea gradului de urâţenie, de la 1 (cel mai urât) la N (cel mai frumos). Dintr-o eroare de aprovizionare, costumele ajung la magazin câte unul pe zi. Proprietarul vrea să expună zilnic în vitrină costumul de urâţenie mediană din cele pe care le are în stoc. Un costum prea urât ar speria clienţii, iar un costum prea frumos... e totuşi Halloween! Ajutaţi-l pe proprietar să expună zilnic costumul potrivit. Notă: proprietarul nu vinde niciun costum, deoarece totul se petrece în aprilie.

Medianul unei mulţimi de 2k + 1 numere este al k+1-lea număr ca valoare. Medianul unei mulţimi de 2k numere, pentru problema noastră, este al k-lea număr ca valoare.

Date de intrare

Fişierul de intrare costume.in conţine pe prima linie numărul N de costume. Pe a doua linie apar N numere, indicând ordinea în care ajung costumele la magazin.

Date de ieşire

În fişierul de ieşire costume.out se vor scrie N numere despărţite prin spaţii. Al i-lea număr reprezintă costumul care trebuie expus în ziua i.

Restricţii

  • 1 ≤ N ≤ 200.000
  • pentru 20% din teste, 1 ≤ N ≤ 20.000

Exemplu

costume.incostume.out
9
2 9 7 1 4 3 5 8 6
2 2 7 2 4 3 4 4 5

Explicaţie

  • În prima zi, unicul costum este 2, care trebuie expus.
  • În ziua a doua, dintre costumele {2, 9}, medianul este 2.
  • În ziua a treia, dintre costumele {2, 7, 9}, medianul este 7.
  • În ziua a patra, dintre costumele {1, 2, 7, 9}, medianul este 2.
  • etc.
Trebuie sa te autentifici pentru a trimite solutii. Click aici