Državno natjecanje iz informatike 2019. / 1. dan / Druga podskupina (3. i 4. razred) - 3. zadatak

Organizatori jednog natjecanja odlučili su sve sudionike počastiti prigodnim nagradama.

Na natjecanju je sudjelovalo N učenika označenih brojevima od 1 do N redom kojim su se pojavili na konačnoj rang listi (učenik 1 osvojio je prvo mjesto, učenik 2 osvojio je drugo mjesto, itd.), ali redoslijed dodjele nagrada nije nužno odgovarao tom poretku.

Svečana ceremonija već je bila u tijeku kad su organizatori usred podjele nagrada primijetili nekolicinu učenika kako se svađaju.

Naime, organizatori nisu vodili računa o vrijednostima nagrada, pa su neki visoko rangirani učenici dobili manje vrijedne nagrade od nekih niže rangiranih učenika.

Pomnim razmatranjem, utvrđeno je da će se dvoje učenika posvađati ako više rangirani učenik dobije nagradu strogo manje vrijednosti od niže rangiranog učenika.

Kako bi ispravili pogrešku, organizatori su preostalim učenicima (onima koji još nisu dobili nagrade) odlučili dodijeliti nagrade tako da ukupan broj parova posvađanih učenika nakon dodjele svih nagrada bude minimalan.

Odredite vrijednosti nagrada koje će dobiti preostali učenici.

ULAZNI PODACI

U prvom je retku prirodan broj N (1 ≤ N ≤ 100 000), broj učenika.

U sljedećem je retku N cijelih brojeva. i-ti broj Xi predstavlja vrijednost nagrade koju je dobio i-ti učenik na rang listi do trenutka kada je uočen problem.

Ako učenik do tog trenutka još nije dobio nagradu, bit će Xi = -1. Inače vrijedi 1 ≤ Xi ≤ 100 000.

IZLAZNI PODACI

U jedini redak ispišite niz X nakon što se svim učenicima dodjele nagrade, čije vrijednosti moraju biti prirodni brojevi između 1 i 100 000.

Ako postoji više mogućih rješenja, ispišite bilo koje od njih.

PRIMJERI TEST PODATAKA

Ulaz

5
2 5 -1 2 5

Izlaz

2 5 2 2 5

Objašnjenje

Pojašnjenje prvog primjera: U ovom rješenju bit će četiri para posvađanih učenika, i to s rednim brojevima 1 i 2, 1 i 5, 3 i 5, 4 i 5.

Alternativno, učeniku br. 3 mogli smo dodijeliti i nagradu s vrijednosti

5. Tada bi također bila četiri para posvađanih učenika. U drugim slučajevima bilo bi ih više.

Ulaz

5
4 6 -1 1 -1

Izlaz

4 6 2 1 1

Ulaz

3
-1 -1 -1

Izlaz

3 2 1